Метапрог-прототип, версия 7 + графические диалоги на Метапроге

Да простит меня Николай Семенович

В оный день, когда над кодом новым
Бог склонял лицо свое, тогда
Память выделяли одним словом
Текстом умножали вектора

Кулер не вращал во тьме крылами
Замирали в RAID-е  HDD
Если, словно розовое пламя,
sudo poweroff мелькал в строке

А для пояснений были схемы
Как домашний подъяремный скот
Потому что крупными мазками
Схема общий смысл передает

Программист седой, начавши смену
Будучи знаком с добром и злом
Прежде чем закодить текста стену 
На планшете рисовал стилом 

Но забыли мы, что осиянно
Только слово средь земных тревог
И в известной книге Гради Буча
Сказано что слово - это код

Мы ему поставили пределом
Скудные пределы естества
И как пчелы в улье опустелом
Дурно пахнут мертвые слова...

PS: Опять он там фантазирует и небылицы про меня рассказывает :)

Тут если что есть кнопка «Показать удаленные комментарии». Держу в курсе.

Диаграммер у Рината отличный вышел. И задачу он свою четко выполнил.

Прочти оригинальный текст своего комментария на который я отвечал. У рината не метапрог, ринат говорил что метапрог делать желания у него нету, или что то подобное, он сделал брейнфак.

Вообще цель stasolog в этих темах провокация на флуд, либо просто человек неадекватен. Моя субъективное суждение.

На самом деле я сам дьявол, ведущий ОПа по неправильному пути, а антиметапрогеры - ангелы, пытающиеся его спасти от моих злых рук!

И кстати говоря как-то так получается занятно, ты начинаешь писать когда stasolog пропадает. Либо вы живете в разных часовых поясах, либо кто-то чей-то доп аккаунт. Доказательств конечно нет, но наблюдение любопытное.

О, вот и старое доброе - «Котечка виртуал метапрога!»

Прочти оригинальный текст своего комментария на который я отвечал. У рината не метапрог, ринат говорил что метапрог делать желания у него нету, или что то подобное, он сделал брейнфак.

Прочти уже что такое Brainfuck, Metaprog в текущем виде такой же «брейнфак» как и диаграммер i-rinat.

На самом деле я сам дьявол, ведущий ОПа по неправильному пути, а антиметапрогеры - ангелы, пытающиеся его спасти от моих злых рук!

Не существует никаких антиметапрогеров, это твоя с ТС фантазия.

О, вот и старое доброе - «Котечка виртуал метапрога!»

Что ТС все таки смену сдал, спать пошел :)

Прочти уже что такое Brainfuck, Metaprog в текущем виде такой же «брейнфак» как и диаграммер i-rinat.

Зачем мне читать? Я и так все знаю. Но тебе дам ссылку - https://ru.wikipedia.org/wiki/Эзотерический_язык_программирования

Не существует никаких антиметапрогеров, это твоя с ТС фантазия.

Существуют. Так же как и хейтеры славянского ПО, я уже показывал примеры, читай предыдущие комментарии.

Я и так все знаю.

Не знаешь увы.

текст программы на нём понятен лишь «посвящённому» либо непонятен вообще

Прям про Metaprog написано. Схемы которые ТС кидает понимает только он. Ну может ты еще, но это не точно.

хейтеры славянского ПО

Еще фантазии.

Не знаешь увы.

Я все знаю, и даже больше.

Прям про Metaprog написано. Схемы которые ТС кидает понимает только он. Ну может ты еще, но это не точно.

Стоит начать читать весь текст, а не отрывки.

Еще фантазии.

Да... Конечно. Кстати, почему у Atonl была такая странная реакция на демонстрацию сварога? Я то понимаю почему, название, музыка, все способствовало подгоранию хейтера славянского ПО. А ты как это объяснишь?

Стоит начать читать весь текст, а не отрывки.

Да почитай пожалуй. Говорят оно полезно.

На бред ниже даже отвечать не хочу.

Да почитай пожалуй. Говорят оно полезно.

Проиграл. Я ведь выше писал что уже знаю все, но ты опять прочел отрывок.

На бред ниже даже отвечать не хочу.

На то что ниже я даже ответить не могу*

Проиграл.

Не забудь ++чсв себе сделать. Конечно проиграл, как можно победить генератор бреда.

https://teenslang.su/id/18541

Я уже писал если хочешь чтобы тебя понимали формулируй свои мысли точно. Без детсадовского сленга.

На дореволюционном?

Я компилировал на MSVC 2019, но тестил чтобы и на godbolt собиралось…

metaprog abcq

https://gcc.godbolt.org/z/sFJGCc

У ОПа Debian и GCC 8. Решение тут - https://apt.llvm.org/.

ну значит не судьба, эту фичу С++17 только в gcc9 добавили…

https://gcc.gnu.org/gcc-9/changes.html

https://imgur.com/a/bsmSkOS

то, что 99 процентов потребителей важнее всего удобство и абсолютно не интересно красноглазие

то, что 99 процентов потребителей важнее всего удобство и абсолютно не интересно красноглазие

Неправда, что пропиарилили то и выбирают.

Пиар тоже имеет место быть но большинство, по крайней мере в моем окружении за циферками не гонится.Гораздо важнее чтобы телефон удобен был и звонил.

Метапрог надо просто самому запустить и потыкать

Когда будет «сам на себе».

что непонятно - спрашивать у меня

Понятно, внятной документации не будет.

Более-менее сложную игру

Ты же вроде утверждаешь, что делаешь серьезный софт, зачем эти постоянные сравнения с играми.

Да ну, тебе не заходит лирика 18 века?

Я вообще ничего не говорил про свои литературные вкусы. Это ты тут восхищаешься какой-то древней литературной порнографией.

Надо просто войти во вкус. Попробуй послушать:

Послушал. Нет. Не интересно.

Сколько байт кэш и как Вы потом поиск проводите?

100 000 (строк длины 100) * 80 (подстрок длины 20) * 16 (байт каждая подстрока, указатель на начало и конец) =

100 000 * 81 *16 = 129.6 мегабайт.

начальных данных:

100 000 (строк) * (24 байта занимает std::string + 101 байт сама строка, 100 символов + ‘\0’) = 12,5 мегабайт

сам поиск такой:

random_string20 const s20;
auto const iter = hash_set.find(s20);
bool const found = (iter != hash_set.end());

забавно что gcc зависит от сторонней либы с двойной лицензией, срамота то какая (¬‿¬)

100 000 (строк длины 100) * 80 (подстрок длины 20) * 16 (байт каждая подстрока, указатель на начало и конец)

1. Вы забыли еще само хэш значение (8 байт?) + управляющие структуры set. Я не знаю деталей, но 16 байт на бакет там вполне может уходить.

2. string_view тут избыточен, хватило бы 4х байт (3 байта - номер строки, 1 байт - смещение в строке) - хотя на фоне структур самого set это небольшой выигрышь.

3. Конечно самое интересное - сколько времени уходит на генерацию хэшей (набивку unordered_set), а сколько уходит на сам поиск.

Да, вы правы насчёт 1 и 2.

По поводу 3: Почти всё время и уходит на генерацию хешей, сама проверка тысячи строк 1мс, даже меньше, в отдельных запусках пишет 0мс…

9/10 всей программы - генерация хешей

1/10 всё остальное: генерация 100 000 случайных строк, аллокация памяти, вывод в консоль и т.д.

Если использовать не std::unordered_set, а поискать какую-нибудь библиотеку где можно параллельно делать insert, то тогда можно ещё ускорить этот пример…

Очевидно, по сравнению с лобовым, этот вариант будет тем эффективнее чем чем больше коротких строк будет проверяться.

Конечно ещё интересно сколько времени занимает сама генерация хэшей, а сколько набивка unordered_set. Возможно переход к четрыхбайтовому хэшу (и векторизация при его генерации - если ее там нет) ускорит все на порядок.

Кроме того можно попытаться сделать какой то вариант хэша для пересчёта которого на сдвинутой подстроке достаточно первого и последнего символов (например сумма всех символов подстроки - это можно посчитать быстро но как хэш оно не айс).

Кстати, разве там не требуется брать unordered_multiset вместо unordered_set?

Если сделать контейнер руками (скажем вектор упорядоченный по хэшам, в каждом элементе хэш и набор описывающий подстроки), то на памяти тоже можно будет прилично сэкономить.

Спасибо!:-)

Вообще самое простое двадцатибитный хэш где каждый бит это четность символа. Считается это влет, сдвиг и & для каждой подстроки.

Дальше заводим массив длины 2^20, номер ячейки это хэш, в ячейках лежат наборы подстрок (4 байта на подстроку), это классическая оллскульная хэш-таблица. Бинго! Не нужно делать O(log_2(N)) операций при поиске, это с головой перекроет коллизии - дальше 8 прямых пооверок и ответ готов.

И по памяти это самое экономное решение, +320 байтов на исходную 100 символьную строку.

Кстати, разве там не требуется брать unordered_multiset вместо unordered_set?

но в предыдущих реализациях я тоже просто искал хотя бы одно совпадение

any_of(
    vector_string100.cbegin(), vector_string100.cend(),
    [&](string const& str100)
    {
        return str100.find(s20) != string::npos;
    }
);

Вот нашёл оригинальное условие: https://postimg.cc/7Cgvcjfh

Ищем первое вхождение, а не общее количество…

Кстати, я вначале хотел искать

Кроме того можно попытаться сделать какой то вариант хэша для пересчёта которого на сдвинутой подстроке достаточно первого и последнего символов

типа как тут, https://e-maxx.ru/algo/string_hashes

но потом перехотел, и решил просто посмотреть наивную версию со стандартными структурами.

Кстати, metaprog вот тебе сайт с алгоритмами на русском: https://e-maxx.ru/algo/

Ищем первое вхождение, а не общее количество…

Но совпадение хэшей не означает совпадение строк. Хотя конечно вероятность совпадения 8ми байтовых хэшей в этой задаче тоже весьма мала…

Я говорил автору что бенч не очень, любой код выдающий ноль совпадений будет корректен:-)

Кстати, metaprog вот тебе сайт с алгоритмами на русском

Чукча Метапрог не читатель, метапрог изобретатель!

Но совпадение хэшей не означает совпадение строк.

Да, я тоже вначале так подумал, потому что мы вчера говорили про хеши, и что они ненадежны

даже в этом сообщении в

Метапрог-прототип, версия 7 + графические диалоги на Метапроге (комментарий)

я искал так:

auto const iter = hash_set.find(s20);
bool const found = (iter != hash_set.end()) ? (*iter == s20) : false;

Но потом, ещё раз прочитал описание find, и понял что это лишнее, find сам дополнительно делает проверку на ==, если хеши равны и с равными хешами может быть много строк в unordered_set.

Вот пример:

https://gcc.godbolt.org/z/2zCPAb

А зачем тогда unordered_multiset? Насколько я понял доки (особо не вчитывался), при хэш-коллизии в unordered_set остаётся один элемент?

Ну видимо для задач где нужно неупорядоченное множество с неуникальными ключами и при этом это не побочный эффект от коллизии. Ну а то, что значение заменяется при совпадении ключей последним, ну такая реализация, в принципе она достаточно непротиворечивая, ключ остается один и он уникален.

Это понятно, но (если я правильно понял доки) можно потерять какие то подстроки.

ну да, просто одна подстрока заменяется другой в таком множестве шансы что-то потерять вполне реальные, можно просто уже к хешу примешивать что-то уникальное и порядковое, тогда точно все будет норм. В общем просто немного подтюнить этот хешсет.

А зачем тогда unordered_multiset? Насколько я понял доки (особо не вчитывался), при хэш-коллизии в unordered_set остаётся один элемент?

Нет. Посмотри ещё раз пример, там у всех хеш ноль, но строки все на месте.

https://gcc.godbolt.org/z/CLnpNB

Уникальность гарантируется не хешем, а оператором == или своим оператором сравнения как в примере.

multiset, это чтобы хранить разные элементы, но для которых мы определили ==.

Пример с multiset, вот у нас есть лекарства. Мы сделали им хеш как их цена, operator ==, как их название, но они могут различаться например страной производства. И мы можем получить список всех одинаковых из multiset: https://en.cppreference.com/w/cpp/container/unordered_multiset/equal_range

Точно ничего не потеряется из-за одинакового хэша в unordered_set

Ок, спасибо.

Набросал с хешами, получилось в 10 раз быстрее. Не параллелится, правда.

#include <omp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ARRAY_SIZE UINT64_C(100000)
#define HAYSTACK_LENGTH UINT64_C(100)
#define NEEDLE_LENGTH UINT64_C(20)
#define NUM_SEARCHES UINT64_C(1000)
#define BLOOM_ORDER UINT64_C(20)
#define BLOOM_SZ (UINT64_C(1) << BLOOM_ORDER)
#define BLOOM_HASHCOUNT 2
#define BLOOM_MAGIC 0x9747b28c
#define NUM_THREADS 1

typedef uint8_t u8;
typedef uint32_t u32;

static u32 mm2(const void *key, u32 len, const u32 seed) {
  const u32 *data = key;
  return *data ^ seed;
}

static void bloom_add(u32 *bloom, u8 *buf, u32 len) {
  u32 a = mm2(buf, len, BLOOM_MAGIC);
  u32 b = mm2(buf, len, a);

  for (u32 k = 0; k < BLOOM_HASHCOUNT; k++) {
    u32 x = (a + b * k) % BLOOM_SZ;
    bloom[x / 32] |= 1 << (x % 32);
  }
}

static u32 bloom_has(u32 *bloom, u8 *buf, u32 len) {
  u32 a = mm2(buf, len, BLOOM_MAGIC);
  u32 b = mm2(buf, len, a);
  u32 hits = 0;

  for (u32 k = 0; k < BLOOM_HASHCOUNT; k++) {
    u32 x = (a + b * k) % BLOOM_SZ;
    hits = !!(bloom[x / 32] & (1 << (x % 32)));
  }

  return hits == BLOOM_HASHCOUNT;
}

int main(void) {

  static const u8 xlat[] = //
      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghij"
      "klmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrst"
      "uvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyzABCD"
      "EFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefgh";

  for (size_t try = 0; try < 10; try ++) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    u8 **array = malloc(sizeof(u8 *) * ARRAY_SIZE);
    u32 *bloom = calloc(1, BLOOM_SZ / 8);
    u32 seed = time(NULL);

    for (size_t k = 0; k < ARRAY_SIZE; k++) {
      u8 *hs = malloc(HAYSTACK_LENGTH + 1);
      for (size_t j = 0; j < HAYSTACK_LENGTH; j += sizeof(u32)) {
        const u32 r = rand_r(&seed);
        *(u32 *)(hs + j) = xlat[(r >> 24)] << 24 |
                           xlat[(r >> 16) & 0xffu] << 16 |
                           xlat[(r >> 8) & 0xffu] << 8 | xlat[r & 0xffu];
      }
      for (size_t j = 0; j < HAYSTACK_LENGTH - NEEDLE_LENGTH; j++)
        bloom_add(bloom, hs + j, NEEDLE_LENGTH);
      hs[HAYSTACK_LENGTH] = 0;
      array[k] = hs;
    }

    char needle[NEEDLE_LENGTH + 1];
    for (size_t k = 0; k < NEEDLE_LENGTH; k++)
      needle[k] = xlat[k & 0xffu];
    needle[NEEDLE_LENGTH] = 0;

    size_t count = 0;
    for (size_t iter = 0; iter < NUM_SEARCHES; iter++) {
      if (bloom_has(bloom, needle, NEEDLE_LENGTH))
        for (size_t k = 0; k < ARRAY_SIZE; k++)
          count += !!strstr(array[k], needle);
    }
    for (size_t k = 0; k < ARRAY_SIZE; k++)
      free(array[k]);
    free(array);
    free(bloom);

    struct timespec te;
    clock_gettime(CLOCK_MONOTONIC, &te);
    printf("count = %zu; %.3f secs\n", count,
           (te.tv_sec - ts.tv_sec) + 1e-9 * (te.tv_nsec - ts.tv_nsec));
  }
}

count = 0; 0.047 secs
count = 0; 0.047 secs
count = 0; 0.046 secs
count = 0; 0.048 secs
count = 0; 0.046 secs
count = 0; 0.047 secs
count = 0; 0.046 secs
count = 0; 0.047 secs
count = 0; 0.047 secs
count = 0; 0.047 secs

Вариант с простым поиском, выполняющийся в восемь потоков, тратил примерно 450-530 мс на итерацию.

Я думал, что смысл теста был в том, чтобы не убегать от вычислений.

Я думал, что смысл теста был в том, чтобы не убегать от вычислений.

да смысла вообще не было :)

Даже так :) ну тогда все действительно видимо будет хорошо.

Раздразнили вы меня пойти и посмотреть на то, как оно вообще выглядит

там оказывается еще помимо find есть и contains, улучшения которого мы все так давно ждали со времен стандарта C++11

которое в прочем все еще

#if __cplusplus > 201703L
      /**
       *  @brief  Finds whether an element with the given key exists.
       *  @param  __x  Key of elements to be located.
       *  @return  True if there is any element with the specified key.
       */
      bool
      contains(const key_type& __x) const
      { return _M_h.find(__x) != _M_h.end(); }
#endif

теперь вы можете писать на две строки меньше :3

Смысл был в том, чтобы увидеть решение на метапороге. Но как раз таки оно никак там не фигурирует

Да ладно вам, признайтесь уже что смысла не было никакого, вы просто анитиметапрогер, вот народ по большей части уже признал, покаялся и все у такого народа теперь хорошо :3

Вообще неплохая учебная задача, надо только доработать ее что бы вхождения были.

забавно что gcc зависит от сторонней либы с двойной лицензией, срамота то какая

LLVM кстати тоже: https://github.com/llvm/llvm-project/tree/master/pstl

А Microsoft на своей либе сделала parallel stl: https://docs.microsoft.com/en-us/cpp/parallel/concrt/parallel-patterns-library-ppl?view=vs-2019

Да я уже тоже видел, ну я конечно понимаю что Интел тоже входит в комитет по стандартизации… Ну, возможно это и есть будущее С++, в той же Джаве тоже такой же подход уже давно, что jsr реализуют все кто сдюжит, а потом тихой сапой и sun/oracle выкатывают свою реализацию если посчитают нужным. Хотя конечно это ломает мой уютный мирок, чтобы пользоваться STL я никогда не докачивал чего-то, теперь вынужден докачивать стороннюю библиотеку, хотя бы сделали бы так чтобы она сама ставилась и неявно линковалась если уж просто не хотят/ не могут по каким-то соображениям её добавить в основной проект.

забавно что gcc зависит от сторонней либы с двойной лицензией, срамота то какая

Если одна из этих лицензий — Apache, совместимая с GPL3, срамоты не вижу.

Неужели такое хочется и интересно читать? Шлак же полный.

Как-то мне приснился Афанасий Фет,
Бьющий Иван Семеныча Баркова.

Он лупил его кастетом,
Приговаривал при этом:
"Я пришел к тебе с приветом
Рассказать, что солнце встало,
Что воспитанным поэтам
Выражаться не пристало".
А Барков просил прощенья,
Сжег поэму про Луку.
Вот такое вот знаменье
Мне приснилось, дураку!

Долго не писал - все делал фичи для 8 версии прототипа (ее давно уже пора выпустить). Возник вопрос. Вот есть цикл for, и хочется как в Лабвью делать массивы на выходе из него. Возможно ли создавать массивы таким образом?

int random_size = rand();
char my_array[random_size];

Или random_size должен быть только константой или constant expression?

А Барков просил прощенья, Сжег поэму про Луку.

Лука Мудищев был значительно позже Баркова и, скорее всего, даже Пушкина. Классический Барков - это 10-строчные куплеты в стиле классицизма с особым переплетением рифм: https://rustih.ru/ivan-barkov-priapu/

Больше всего веселит именно само сочетание «высокого» стиля с пикантной тематикой. Позже мода на ломоносовские/барковские 10-строчные куплеты уже прошла. Тот же Пушкин в сравнении с Барковым какой-то более «простой», но почитать его поэзию тоже весело (разумеется, нешкольную, как Тень Баркова). Открыв для себя «пикантную» поэзию, я открыл для себя русских классиков, до этого я официальную школьную программу по большей части предпочитал скипать из-за скучности.

Кстати, диагарммы на Метапроге (кроме лабвьюшного прототипа, лицензированного под GPL3) я пока пилю под MPL2. Это нужно для нижних слоев типа стандартной библиотеки. Ведь с нее можно в любой момент на любом этапе перескочить на GPL3, так ведь?

На 5-символьных подстроках (вместо 20) вхождений хватает.