Предложение остаётся в силе. Всё что я предлагаю — подкорректировать вектор усилий. Непонятно, зачем брать структуру, изначально ориентированную, на целочисленные идентификаторы и исследовать её просто заменив эти идентификаторы на GUID-ы. Есть действительно актуальные задачи, странно почему вы их избегаете.
1. Что такое «быстрый поиск»? Поиск по чему? По ключу? По значению?
Универсальный, возможно, ориентированный на рассмтриваемую задачу, если предусмотреть в нём индексирование по прикладным данным.
2. Проще говоря, идеальная хэш-функция. Теоретически возможна в том случае, когда размеры множеств идентичны, но как вы планируете гарантировать это условие?
Практически, такую хэш-функцию можно разработать, если предусмотреть в ней так-же индексирование по прикладным данным.
В демо-примере максимальное значение равно максимальному количеству и соответствует количеству тестовых данных. Тестовые данные подготовлены без пробелов.
Реальные данные допускают существование пробелов.
Реальный размер массива должен быть не меньше максимального значения. Максимальное значение (результат инкрементальной функции) не вычисляется, а смотрится в БД и устанавливается с запасом. Запас согласовывается с требованиями Заказчика и определяется исходя из среднего количества прироста на единицу времени.
Если все эти типовые, для такого типа задач, условия были непонятны из содержания публикации и вызывали затруднения и вопросы, то приношу свои извинения.
Могу предложить рассмотреть ещё пару задач, которые более интересны (ИМХО) с практической точки зрения.
1. Быстрый поиск в ассоциативном массиве. Так, чтобы было быстрее стандартного поиска хотя бы на пару порядков.
2. Разработать функцию для формирования уникального целочисленного значения на заданном числовом интервале для символьного входного значения. То есть — на вход функции строка — на выходе уникальное число. Тогда вообще без ассоциативных массивов можно обойтись и работать с идентификаторами любых типов, как с целочисленными.
Начальные условия для обоих задач: имеем неограниченные ресурсы (для начала можно сделать такое допущение), надо выжать минимальное время, стремящееся к теоретически возможному. Можно установить дополнительные условия (мы же не магией занимаемся).
Просто проект, который послужил основой для публикации, завершён. Будет другой проект — будут другие данные и другая структура. Например, условие «идентификаторы типов муравьев и регионов муравейника — байт». Фактически, это очень упрощает задачу. А если это тоже GUID или смысловой ключ или даже всего лишь Int32? При этом, описанный в публикации подход, элементарно вылетает в трубу.
Но я бы не стал слишком увлекаться прикладной частью. Мы ведь пытаемся найти решение некой абстрактной общей задачи. Поэтому вы абсолютно свободны в выборе структуры и формата данных.
Это вовсе не обязательно и зависит от выбранного подхода.
Например, выбираем подход с хэшированием GUID-ов. На линейные списки хэш вычисляется просто и быстро. Отсортировали, выгрузили список из СУРБД в CSV, а потом отхешировали присвоением GUID-у числового идентификатора по номеру строки (создали новый CSV).
Сложнее сделать следующую итерацию — отхэшировать список связей (сопоставить каждый GUID с уже известным числовым идентификатором). Чем больше данных — тем дольше поиск по ассоциативному массиву (время может вырасти до неприличных значений). Кроме того, если ассоциативный массив не поместился в память, то тут и начинается основное плохокодирование. Мне красивое решение неизвестно.
Я так понимаю, что данные групируются по «регионам» муравейника — ок. Что выводится для каждого муравья?
Да — группировка по регионам. Для каждого муравья выводятся идентификатор муравья и идентификатор ячейки.
Как в выводе должны выглядеть муравьи, привязанные к нескольким комнатам? Например, если муравей привязан к нескольким комнатам, и эти комнаты в разных регионах — он должен появиться в группе каждого из этих регионов?
Да — в группе каждого региона
Например, могут ли они быть заранее отсортированными по нужному мне параметру? (и да, я ожидаю ответ «да, могут», потому что я с трудом могу себе представить реальную ситуацию, когда это невозможно)
Для целочисленных идентификаторов предварительно сделанная сортировка значения не имеет, так как в индексный массив они будут сохранены в соответствии со значением чилового идентификатора.
Для GUID-идентификаторов сортировка, возможно, может иметь значение, но это будет зависеть от выбранного алгоритма хэширования.
Ваше решение всегда выводит данные только по одному типу муравьев. Так и должно быть, или это его недоработка?
Можно выбрать любой тип заданием параметра: anthill-makeresult.exe 4 (1- царица, 2 — личинка, 3 — нянька, 4 — рабочий, 5 — солдат)
или в коде — изменить тип по дефолту:
int filtrAntType = 5; // дефолтный фильтр - солдат
Как именно должен выглядеть результат работы (вывод)?
Для простоты и переносимости использован CSV. А подойдёт любой формат, главное чтобы можно было легко осуществлять обмен с СУРБД.
Как в выводе должны выглядеть результаты для муравьев, живущих в более чем одной клетке (раз уж вы утверждаете, что это возможно)?
Отношение многие-ко-многим не накладывает количественных ограничений на связи. Главное чтобы идентификаторы в списках были уникальными и пары идентификаторов в таблице связи были уникальными, но за это отвечает СУРБД или утилита подготовки тестовых данных (просто утилита не перемешивает идентификаторы — пусть это вас не смущает, ни пропуски ни последовательность идентификаторов роли не играют).
Откуда в реальности поступают исходные данные, и до какой степени ими можно манипулировать (напоминаю, что вы утверждали, что данные выгружаются из СУБД)?
Хранятся списки в таблицах СУРБД или в CSV файлах значения не имеет. Вы можете легко подготовить тестовые CSV данные, загрузить их в БД, обработать и оставить там, а можете наоборот, из БД в CSV, обработать, а результат загрузить в БД. Но для сути задачи БД не нужна.
Можно ли рассчитывать на то, что идентификаторы (муравьев и клеток) целочисленные и последовательные (в значении contiguous)?
Данные целочисленные, последовательность и пропуски значения не имеют.
Просто вроде как это уже не интересно. Гораздо интереснее рассмотреть вариант, где целочисленные значения идентификаторов заменены на GUID-ы (или другие нецифровые значения, типа не суррогатных, а смысловых ключей, например «A-001-2015.01.01»)
Я вас понимаю: лето, мало статей, скука. Сам от этого страдаю.
У меня есть конструктивное предложение. Вы предлагаете алтернативное моему решение по озвученным вами выше вопросам (пусть оно будет не идеальным). Его мы и рассмотрим (не забудте прислать ссылку на код).
ЗЫ Я уверен, что вас заинтересует моё предложение, поэтому прошу открыть новую ветку для обсуждения.
Конечно влияет и об этом ясно сказано в публикации «Существенное влияние на решение могут оказать, например, другая структура или другой формат прикладных данных».
Если у вас будут данные, где уникальным идентификатором является произвольная срока, то без хэш-индекса (ассоциативными массива) будет сложно обойтись.
Лично мне это никак не указывает. Потому что если вы работаете с СУБД, то совершенно не понятно, зачем вы это делаете не в ней.
Модель данных приведена в публикации на рисунке. Кроме того вы можете сгенерировать тестовые данные (ссылка на утилиту в публикации), загрузить их в СУБД и через день-два получите ответ.
Я не очень понимаю, что именно вы имеете в виду. Вы не могли бы показать на примере?
Плохокодить я не буду. А работа с хэш-таблицами и ассоциативными массивами хорошо описана. Если-бы мне было известно хорошее решение по работе с нечисловыми идентификаторами, то в публикации было бы показано оно.
Вы все еще считаете, что объем данных не влияет на трудоемкость?
Утверждение дано в самом начале публикации «Главное, как можно раньше (до начала разработки), определить правильный подход к задаче». Ещё раз. Это означает, что если на архитектуру и разработку надо затратить, например, 3 месяца — значит 3. А, если через 2 месяца работ выясняется, что всё можно сделать за неделю, то… варианты додумайте сами.
ЗЫ Ваши вопросы перестали быть интересными. Давайте закроем дискуссию. Или переведём её в другой формат (но только чтобы было действительно интересно).
Вы разработали проект, но результат получился «не очень» и вы убеждаете и себя и Заказчика, что лучшего быть не может, или это — из области мэйнфреймов/кластеров.А Заказчик и не спорит и даже кивает головой — типа верит. А через некоторое время появляется человек средних лет, с трёхдневной небритостью и потёртым ноутбуком и берётся через неделю продемонстрировать, как увеличить быстродействие вашей системы на пару порядков. В эту неделю плохо спится.
И опять, увы… Идентификаторы могут иметь любую последовательность и любые пропуски, главное, чтобы размер массива был не меньше максимального числового значения идентификатора. В этом одновременно и сила и слабость индесного массива — не для всех задачь он применим, но если задача соответствует — скорость поиска будет стремиться к теоритически возможной.
Кстати, если данных не так много (несколько миллионов), то их лучше обрабатывать в СУРБД.
вам не кажется, что ваше решение масштабируется немножко нелинейно?
За стремление к линейности или там, «горизонтальности» придётся платить так-же как за стремление к реалтайму (в ИТ чудес не бывает — это не магический чёрный ящик).
Это теоретические фантазии, а ответ очень простой и лежит на поверхности.
Структура данных, рассмотренная в публикации — реляционная и данных много. Это однозначно указывает на то, что данные взяты из промышленной СУРБД. СУРБД, соответствующих вашим запросам, на текущий момент ещё не разработано (приведите примеры).
Кроме того — данные не могут взяться ниоткуда, тем более реляционные. Так что в природе, задачь соответствующих, заданной структуре и вашим требованиям, просто не существует, потому что не существует таких данных.
А это точно допустимое время выполнения? А точно нет другого способа оптимизировать алгоритм?
Одна ночь — это о-очень хороший результат. Обычно, если удаётся уложиться в это время — дальше уже никто не парится, даже если есть известные пути оптимизации.
А кому действительно нужен реалтайм — тот вынужден платить о-очень много за оборудоване и разработку, и процент успешного выхода не 80/20, а 20/80.
Во сколько раз вы только что увеличили требования по памяти? А, главное, зачем вам сопоставлять гуиды с числами?
Требования по памяти на рабочий процесс не увеличилось, совсем. Так как хэш-индекс (именно о нём идёт речь при сопоставлении GUID-а с числом) придётся готовить заранее. Но, для списочных данных, это очень простой и быстрый процесс, так как все GUID-ы уникальные — об этом позаботится СУРБД из которой данные выгружаются.
Другое дело подготовка хэш-индекса на связной список — скорость поиска в ассоциативном массиве на порядки медленнее, чем скорость обращения по индексу в массиве из примера.
Когда хэш-индексы подготовлены — отлично будет работать пример из публикации.
Чисто теоритически есть ещё подход — разработать хэш-функцию, которая на заданном числовом интервале, даст однозначное уникальное преобразование GUID-а в число. Но, к сожалению, вероятность успешной разработки такой функции равна нулю.
Универсальный, возможно, ориентированный на рассмтриваемую задачу, если предусмотреть в нём индексирование по прикладным данным.
Практически, такую хэш-функцию можно разработать, если предусмотреть в ней так-же индексирование по прикладным данным.
Реальные данные допускают существование пробелов.
Реальный размер массива должен быть не меньше максимального значения. Максимальное значение (результат инкрементальной функции) не вычисляется, а смотрится в БД и устанавливается с запасом. Запас согласовывается с требованиями Заказчика и определяется исходя из среднего количества прироста на единицу времени.
Если все эти типовые, для такого типа задач, условия были непонятны из содержания публикации и вызывали затруднения и вопросы, то приношу свои извинения.
Максимальное значение известно заранее — миллиард.
«Цель публикации — поделиться опытом как, за приемлемое время, обработать два связанных списка по миллиарду записей в каждом.»
1. Быстрый поиск в ассоциативном массиве. Так, чтобы было быстрее стандартного поиска хотя бы на пару порядков.
2. Разработать функцию для формирования уникального целочисленного значения на заданном числовом интервале для символьного входного значения. То есть — на вход функции строка — на выходе уникальное число. Тогда вообще без ассоциативных массивов можно обойтись и работать с идентификаторами любых типов, как с целочисленными.
Начальные условия для обоих задач: имеем неограниченные ресурсы (для начала можно сделать такое допущение), надо выжать минимальное время, стремящееся к теоретически возможному. Можно установить дополнительные условия (мы же не магией занимаемся).
Просто проект, который послужил основой для публикации, завершён. Будет другой проект — будут другие данные и другая структура. Например, условие «идентификаторы типов муравьев и регионов муравейника — байт». Фактически, это очень упрощает задачу. А если это тоже GUID или смысловой ключ или даже всего лишь Int32? При этом, описанный в публикации подход, элементарно вылетает в трубу.
Но я бы не стал слишком увлекаться прикладной частью. Мы ведь пытаемся найти решение некой абстрактной общей задачи. Поэтому вы абсолютно свободны в выборе структуры и формата данных.
Например, выбираем подход с хэшированием GUID-ов. На линейные списки хэш вычисляется просто и быстро. Отсортировали, выгрузили список из СУРБД в CSV, а потом отхешировали присвоением GUID-у числового идентификатора по номеру строки (создали новый CSV).
Сложнее сделать следующую итерацию — отхэшировать список связей (сопоставить каждый GUID с уже известным числовым идентификатором). Чем больше данных — тем дольше поиск по ассоциативному массиву (время может вырасти до неприличных значений). Кроме того, если ассоциативный массив не поместился в память, то тут и начинается основное плохокодирование. Мне красивое решение неизвестно.
Да — группировка по регионам. Для каждого муравья выводятся идентификатор муравья и идентификатор ячейки.
Да — в группе каждого региона
Для целочисленных идентификаторов предварительно сделанная сортировка значения не имеет, так как в индексный массив они будут сохранены в соответствии со значением чилового идентификатора.
Для GUID-идентификаторов сортировка, возможно, может иметь значение, но это будет зависеть от выбранного алгоритма хэширования.
Можно выбрать любой тип заданием параметра: anthill-makeresult.exe 4 (1- царица, 2 — личинка, 3 — нянька, 4 — рабочий, 5 — солдат)
или в коде — изменить тип по дефолту:
Для простоты и переносимости использован CSV. А подойдёт любой формат, главное чтобы можно было легко осуществлять обмен с СУРБД.
Отношение многие-ко-многим не накладывает количественных ограничений на связи. Главное чтобы идентификаторы в списках были уникальными и пары идентификаторов в таблице связи были уникальными, но за это отвечает СУРБД или утилита подготовки тестовых данных (просто утилита не перемешивает идентификаторы — пусть это вас не смущает, ни пропуски ни последовательность идентификаторов роли не играют).
Хранятся списки в таблицах СУРБД или в CSV файлах значения не имеет. Вы можете легко подготовить тестовые CSV данные, загрузить их в БД, обработать и оставить там, а можете наоборот, из БД в CSV, обработать, а результат загрузить в БД. Но для сути задачи БД не нужна.
Данные целочисленные, последовательность и пропуски значения не имеют.
Просто вроде как это уже не интересно. Гораздо интереснее рассмотреть вариант, где целочисленные значения идентификаторов заменены на GUID-ы (или другие нецифровые значения, типа не суррогатных, а смысловых ключей, например «A-001-2015.01.01»)
У меня есть конструктивное предложение. Вы предлагаете алтернативное моему решение по озвученным вами выше вопросам (пусть оно будет не идеальным). Его мы и рассмотрим (не забудте прислать ссылку на код).
ЗЫ Я уверен, что вас заинтересует моё предложение, поэтому прошу открыть новую ветку для обсуждения.
[Close]
[Close]
Если у вас будут данные, где уникальным идентификатором является произвольная срока, то без хэш-индекса (ассоциативными массива) будет сложно обойтись.
Модель данных приведена в публикации на рисунке. Кроме того вы можете сгенерировать тестовые данные (ссылка на утилиту в публикации), загрузить их в СУБД и через день-два получите ответ.
Плохокодить я не буду. А работа с хэш-таблицами и ассоциативными массивами хорошо описана. Если-бы мне было известно хорошее решение по работе с нечисловыми идентификаторами, то в публикации было бы показано оно.
Утверждение дано в самом начале публикации «Главное, как можно раньше (до начала разработки), определить правильный подход к задаче». Ещё раз. Это означает, что если на архитектуру и разработку надо затратить, например, 3 месяца — значит 3. А, если через 2 месяца работ выясняется, что всё можно сделать за неделю, то… варианты додумайте сами.
ЗЫ Ваши вопросы перестали быть интересными. Давайте закроем дискуссию. Или переведём её в другой формат (но только чтобы было действительно интересно).
[Close]
Вы разработали проект, но результат получился «не очень» и вы убеждаете и себя и Заказчика, что лучшего быть не может, или это — из области мэйнфреймов/кластеров.А Заказчик и не спорит и даже кивает головой — типа верит. А через некоторое время появляется человек средних лет, с трёхдневной небритостью и потёртым ноутбуком и берётся через неделю продемонстрировать, как увеличить быстродействие вашей системы на пару порядков. В эту неделю плохо спится.
Кстати, если данных не так много (несколько миллионов), то их лучше обрабатывать в СУРБД.
За стремление к линейности или там, «горизонтальности» придётся платить так-же как за стремление к реалтайму (в ИТ чудес не бывает — это не магический чёрный ящик).
Это теоретические фантазии, а ответ очень простой и лежит на поверхности.
Структура данных, рассмотренная в публикации — реляционная и данных много. Это однозначно указывает на то, что данные взяты из промышленной СУРБД. СУРБД, соответствующих вашим запросам, на текущий момент ещё не разработано (приведите примеры).
Кроме того — данные не могут взяться ниоткуда, тем более реляционные. Так что в природе, задачь соответствующих, заданной структуре и вашим требованиям, просто не существует, потому что не существует таких данных.
Одна ночь — это о-очень хороший результат. Обычно, если удаётся уложиться в это время — дальше уже никто не парится, даже если есть известные пути оптимизации.
А кому действительно нужен реалтайм — тот вынужден платить о-очень много за оборудоване и разработку, и процент успешного выхода не 80/20, а 20/80.
Требования по памяти на рабочий процесс не увеличилось, совсем. Так как хэш-индекс (именно о нём идёт речь при сопоставлении GUID-а с числом) придётся готовить заранее. Но, для списочных данных, это очень простой и быстрый процесс, так как все GUID-ы уникальные — об этом позаботится СУРБД из которой данные выгружаются.
Другое дело подготовка хэш-индекса на связной список — скорость поиска в ассоциативном массиве на порядки медленнее, чем скорость обращения по индексу в массиве из примера.
Когда хэш-индексы подготовлены — отлично будет работать пример из публикации.
Чисто теоритически есть ещё подход — разработать хэш-функцию, которая на заданном числовом интервале, даст однозначное уникальное преобразование GUID-а в число. Но, к сожалению, вероятность успешной разработки такой функции равна нулю.