Сергей apelserg

В общем, новая версия

Правильно ли я понял:

1. Два списка должны быть отсортированны в «неубывающую последовательность» до начала обработки: cells и antsToCells(отсортированный по cells). Это условие лежит в основе работы алгоритма.

2. В память (HashSet) полностью помещается ants, а файлы cells и antsToCells (за счёт строгой последовательности cell-идентификаторов) читаются последовательно один раз, в ходе выполнения ants-цикла.

Вопросы:

1. Во сколько вы оцениваете потребность в памяти (сколько RAM должно быть на компе), чтобы обеспечить обработку миллиарда записей?

2. Как вы будете решать задачу, для 10 миллиардов?

3. 100000000 (сто миллионов) записей (ants, cells, antsToCells), на которых производится текущее тестирование, занимают 14 Гб. Значит миллиард займёт 140 Гб. Допустим есть такой поставщик/источник данных (140 Гб в миллиарде записей). Сможет ли этот поставщик данных поставлять отсортированные данные? А, если нет (сервера опечатаны)? Как вы будете решать такую задачу?

Так уже решил же

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

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

Я не возражаю

Другой подход к чему?
Какой проблемы?

Мммм… Похоже, я перестал понимать, что вы не понимаете. Решите задачу, так как вы сами её понимаете. Наверное это будет самым разумным подходом. Я всегда готов оказать посильную помощь, задавайте любые вопросы.

Кто вам мешает отсортировать файл в миллиард строк

Правильно ли я понимаю, что именно этот подход, вызывает затруднение?

Он полностью проверяем

Вы это называете проверяемостью?

Ээээ… то есть вывести данные из таблицы можно, а вывести данные из индекса (который сопоставимого размера) — не хватает ресурсов? Но как?
Пока, возникли проблемы с простой сортировкой списка.

В реальной жизни нет проблем с сортировкой списка, потому что в реальной жизни сортировка списка происходит за рамками задачи.

Я перестал понимать ход ваших мыслей. О каких индексах и о каких рамках вы говорите? Сделайте простой сортированный список на GUID-ах и О'кей. Но вы утверждаете, что проблема в скорости. Хорошо, предложите другой подход. Я повторяю — решение этой проблемы мне неизвестно.

Но они вас почему-то не устраивают

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

Обычный такой индекс на БД

Объясняю. Индекс для сортировки не поможет, так как ресурсы, требуемые для запроса-вывода, значительно превышают ресурсы любого мыслимого сервера.

Строить индекс или нет для обеспечения простого несортированного запроса на таком объёме данных? Не буду вводить вас в заблуждение — этот вопрос требует изучения.

Ну нет, так не работает

Браво! Вы меня не перестаёте удивлять! Я честно признался, что красивое решение мне неизвестно. Вы, совершенно добровольно, взялись за задачу (от которой я вас отговаривал), сами сформировали требования (против которых я всего лишь не стал возражать), но задача оказалась не постой (так бывает). Не понимаю, какой ответ вы от меня ожидаете получить? Я повторяю — мне красивого и технологичного решения этой задачи неизвестно (я её конечно же продумывал).

Какие проблемы у вас могут возникнуть «в реальной жизни»?

Пока, возникли проблемы с простой сортировкой списка. Пока не получается найти решения. Это можно «записать в книжечку». По-моему это очень хороший «сухой остаток» и потраченное время нельзя назвать «бессмысленно потраченным».

Окей, на какие множители вы согласны?

Меня устроят любые. Всё, что я делаю — задаю (очень) простые вопросы, а решения по вашей разработке (на которую вы совершенно добровольно согласились) конечно должны принимать вы.

В такой ситуации полезно пойти к начальнику

Вопрос, конечно, не технический, а организационный. Но я бы не стал ходить к начальнику, если, конечно, это не ваш близкий родственник или хороший знакомый. В такой ситуации, приоритет контракта с Заказчиком и наличие мотивированного ПМ-а в этом контракте, для любого начальника, на порядок (или два) выше личного недовольства, пусть даже гениального, разработчика. А ПМ-то чем виноват? В 99% он в той-же шкуре, что и разработчик.

Как-как, по индексу, конечно.

Поясните, как это? ORDER BY GUID_ID по таблице в миллиард записей? Как вам удаётся такие индексы строить?

И да, если это проблема, то почему вы согласились с тем, что входные данные могут быть отсортированными?

Я вовсе не соглашался, я просто переубеждать вас не стал. Вы так уверенно взялись за задачу. А вдруг? Зачем же прерывать полёт творческой мысли.

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

Какой сценарий вам интереснее? Мне кажется, что второй правильнее.

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

когда я сдаю систему, есть ПМИ

Интересно посмотреть на ПМИ, где прописано, что зависимости получаются случайным образом и не проверяются (где вы таких Заказчиков находите?).

Кроме того, любые требования ТЗ, ПМИ, рабочий план-график и т.д. всегда можно «уточнить». Разве вам не знакома ситуация, когда завтра/на следующей неделе должна сдаваться система,
но к вам подходит ПМ и ставит в известность, что с Заказчиком подписаны «небольшие» изменения, «не влияющие на сроки», которые надо срочно доработать. Иначе контракт закрывается, нет финальной оплаты, прощай премия.

но скорость генерации падала даже не как n log n от объема

Я считаю, что задача, фактически, состоит из двух этапов:
1. Подготовка тестовых данных;
2. Подготовка результата;

Вы поторопились приступить ко второму, не разобравшись с первым.

А первый этап (подготовка результатов) уже начинает преподносить свои сюрпризы. Оказывается расчитывать на последовательность данных (препроцессинг) не стоит. Скорее наоборот — препроцессинг невозможен. Или привидите пример, как вы собираетесь выгружать отсортированные данные такого объёма из, например, СУРБД?

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

Я вообще не понимаю, зачем вам нужно здесь случайное распределение.

Объясняю. Муравьёв — 1000, ячеек — 1000, связей — 1000. Муравьёв типа 255 — 373. В результате — 40 записей. Вы сдаёте систему. Ни один приёмщик вам акты не подпишет.

В чем их подтасованность?

Хорошо, вы утверждаете, что таким образом (используя ненастоящие GUID-ы) имитируете препроцессинг «я не зря спрашивал, разрешен ли препроцессинг». Что вам мешает на этапе генерации провести этот «препроцессинг» на основе «честных» GUID-ов (конечно это немного усложнит генератор).

Нет, это не важно. Важно, чтобы последовательность была неубывающей.

Вы меня удивляете. Я, например, не вижу абсолютно никакой разницы между понятиями «ненастоящие GUID-ы» и «Важно, чтобы последовательность была неубывающей». Это — «подтасованные данные».

Неужели вас может интересовать результат, полученный на «подтасованных данных»?

Поселённых окажется около 40, что соответствует вашим результатам

Это понятно (посмотрел код), данные для таблицы связи формируются случайным образом. Но отлаживать функциональную часть удобнее и правильнее на небольшом объёме целостных данных.

Для парсера важно, что и в файле cells, и в antsToCells имена ячеек идут в лексикографическом порядке (Guid не убывают).

Если для парсера важно, чтобы GUID-ы были «ненастоящими» и последовательными — такое условие нарушает «чистоту» эксперимента.
GUID-ы, которые на самом деле GUID-ами не являются, в природе не существуют, а если существуют, то это можно рассматривать как «информационное преступление».

Уточнее:

Пока 1000. Я устанавливал разные типы (например 255) — результат — всегда одна запись на один файл.

Всего муравьёв типа 255 в файле ants — 273

Всего муравьёв типа 255 в файле ants — 373 (а не 273)

В 6 файлах из 35 — по 2 записи (в остальных по одной)

для ячеек удобнее использовать последовательные. Это критично только в генерации.

Не понимаю, вы можете пояснить в чём удобство? (По коду я не понял, а комментарии отсутствуют)

У меня такого поведения не наблюдается. Какого размера у вас стартовый массив данных?

Пока 1000. Я устанавливал разные типы (например 255) — результат — всегда одна запись на один файл.

Всего муравьёв типа 255 в файле ants — 273
Файлов на выходе — 35 (area-004, area-009, area-013,… area-218, area-230, area-238)

Это вид консоли:
С:\anthill-guid>AntHeap.Parser.exe .\ .\ 255
Parsing ants of type 255 from .\ to .\
Parsing complete in 00:00.038

Как-то так

1. Не понимаю смысла формирования GUID-ов разного типа для муравьёв и для ячеек:

(муравьи)
2d9bd55609174c029abc69c6fc2d02c5

(ячейки)
00000000491c61c0d1043fc221c3bff4

2. При подготовке результата (area-071, area-153,… ) всегда присутствует только по одной записи в каждом файле. Это недоработка?

Для разных прикладных задач нужны разные структуры данных, зачем в одну-то все запихивать?

Для разных прикладных задач потребуются разные структуры.

Вот только этот «банальный вывод» противоречит тезису из «краткого резюме»

Как раз никакого противоречия нет. Планируйте трудоёмкость «правильно» и живите спокойно.
«Правильно» в данном случае — хорошее знание матчасти и умение её применять в деле.
Ну и, конечно, без простого везения не обойтись (у английских капитанов, в личном деле, даже была такая графа — везучесть).

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

Рамки требований определяет прикладная задача. Фактически, надо быть готовым ко всему. Все перечисленные варианты придётся рассмотреть.

Разочарование. Такое бурное обсуждение ради такого банального вывода.

Что такое «один проход»?

«Один проход» — это «лукап» по всему массиву (в миллиард).

К какой задаче? Оптимизации одного обращения или оптимизации миллиона обращений?

Речь идёт об оптимизации миллиарда обращений.

Выходит, что вы вовсе не против добавления памяти. Тогда поясните в чём должен состоять «сухой остаток» нашего обсуждения?

Так вы сами раскрыли суть этой задачи «Ничего универсального тут быть не может».
Здесь есть, как минимум, несколько интересных мест, над которыми можно поработать.
Например, «поиск по ключу — O(1)». Предположим, что один проход по ассоциативному массиву в миллиард, равен одной секунде.
Миллиард проходов даст миллиард секунд. Грустно. Но, если к этой задаче подключить архитектуру (например разделить процесс),
то можно значительно улучшить время (интересен так же и вопрос цены на единицу улучшенного времени). И это вовсе не «микрооптимизации», а здравый архитектурный подход.

Обычно бывает именно так, как вы описываете. Но, довольно часто, именно в настоящее время, Заказчик контракт подписывает, но остаётся недовольным и продолжает поиск исполнителя. Вас при этом, он в известность не ставит. И, если поиск удаётся, все недоработки по проекту — это основания, чтобы контракт разорвать, а если выясняется (не без помощи нового исполнителя), что была завышена смета, то легко получить претензию по неустойке.

А надо-то было всего докупить два чипа памяти.

А к вам не могут зайти простые ребята с трёхдневной небритостью? «Ночной кошмар программиста». Мне известны примеры, когда так были потеряны большие проекты.

Вы легко списываете полгода потраченного времени, но несколько гигабайт памяти, которые экономят эти полгода, считаете «дорогими». Где здесь логика? Вы можете объяснить?

А меня наоборот, заинтересовала как раз эта задача. Если удастся продвинуться, я буду держать вас в курсе.

А как вы поступаете, если, например, расчитанная трудоёмкость полгода, а найденное решение уложилось в 2 недели и нашли это решение «в соседнем отделе»? Или такого быть не может?

Я расчитывал на то, что задача «Быстрый поиск в ассоциативном массиве» вас заинтересовала. Если нет, то зачем же тогда вы продолжили обсуждение этой задачи?

Вот это место, где вы спрашиваете:

Я еще раз спрашиваю: поиск по ключу или по значению?

Я ещё раз обдумал и пришёл к выводу, что придётся делать поиск и по ключу и по значению. Это нужно для разных функциональных этапов. Смотрите, в задаче существует состояние, когда в списке связи известен GUID (значение), но неизвестен ключ. Здесь однозначно нужен поиск по значению. И есть состояние когда нужен поиск по ключу, чтобы быстро получить значение.

А разве вы закладываете в проекты только универсальные решения? Каждый проект имеет свои ресурсные ограничения. Поэтому лёгкие функциональные решения не редко ценятся выше трудоёмких универсальных. Тем более лишняя трудоёмкость вовсе не гарантирует лучшего качества.

Извините, я конечно погорячился с универсальностью. Вопрос — GUID это ключ или значение? Я буду считать его значением, хотя изначально он является идентификатором, то есть ключом (поправьте как вам удобней, это не принципиально). Значит ключ — целочисленное число.

Если я правильно понял замысел задачи, то всем GUID-ам надо сопоставить ключи, и производить все выборки по ключам. Следовательно надо делать поиск по ключу.

Понятное решение. Извините, что я пытался вас переубедить.

Я еще раз спрашиваю: поиск по ключу или по значению?

Что мешает заложить универсальный

Ну, вы же понимаете, что у вас тогда расход памяти еще веселее становится?

Да, я понимаю. Мне повезло, условия проекта были такие. В память всё влезло и никто не парился. Уверен, что существенный процент задач могут быть решены подобным образом.

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

Это странно, делают конечно распредлённые системы на GUID-ах, но делают и по-другому, например на составных целочисленных ключах, или выделяют диапазоны. Так, что я утверждаю — вполне типовые.