Listview VS архив в памяти, почему архив проигрывает?

[Pantalone]

Имеется около 100 000 значений, которые могут повторяться. Задача составить их список с подсчетом сколько раз каждое значение повторяется.
Делаю так, прежде чем добавить следующее значение в список перебираю уже ранее добавленные и если оно там встречается, то прибавляю единичку к счетчику для этого значения, если не встречается, то добавляю как новое.
Что обнаружилось, Listview с этим справляется в несколько раз быстрее, чем архив в памяти.
Прилагаю примерчик, значения генерируются рандомно, количество значений уменьшено до 20 000 и даже при таком количестве архив работает почти в два раза медленнее.
Может кто подскажет, как ускорить работу с данными в архиве?

[Хакер]

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

[ger_kar]

Дело в этой инструкции ReDim Preserve MyArch(gMax)
У тебя по сути при каждом обновлении происходит следующее:
Выделяется память под новый массив с размерностью старый + 1, затем туда копируются значения старого массива, за исключением последнего элемента, а старый массив уничтожается с освобождением памяти. Получается, что каждый раз при добавлении нового элемента это повторяется раз за разом и как раз эти накладные расходы отъедают основную часть времени. И с ростом массива это время увеличивается, а сам процесс замедляется.

[Хакер]

ger_kar, ты не прав. Это только часть проблемы, причём не самая значительная.

Можешь убедиться сам — поправь его код так, чтобы изначально выделялся массив огромного размера (20 0000 элементов). Скорости это добавит немного: у меня время с 30 секунд сокращается до 24. Это всё равно в 3 раза дольше, чем LV.

К тому же наращивает он массив не по одному значению, а сразу на 500 (что конечно ужасно в целом, но лучше, чем ты описываешь).

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

Если рассмотреть худший случай, когда совпадений не происходят и генерируются только случайные числа, то 19999-ая вставка вынуждена проверить 19998 элементов, а 20000-ая вставка — 19999 элементов.

Получается i-ая вставка проверяет i-1 элементов массива.

Общее число операций сравнения составляет арифметическую прогрессию: 1 + 2 + 3 + ... + (i-1).

И тогда, если подсчитать по форуме суммы арифм. прогрессии, для 20 000 элементов это будет почти 200 млн операций.

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

[ger_kar]

Я бы вообще сделал так:
Выделил сразу массив под максимальное кол-во элементов и так как генерируются по сути целочисленные значения использовал бы их как индексы этого массива. Так им образом не перебирал бы массив раз за разом, а сразу по индексу находил бы искомое значение и увеличивал бы его на 1.
И после генерации всех чисел прошел бы по массиву и посчитал количество значений не равных 0. Далее создал бы второй массив по количеству этих значений и перенес данные второго массива туда.

[Хакер]

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

Размер такого массива должен быть равен не числу генерируемых элементов, а размаху диапазона индексов: если значений будет 100, но они могут принимать любые 32-битные величины, то тебе банально не хватит памяти (а если бы хватило — был бы дичайший перерасход). Не говоря уже о случае, когда индексом будет GUID.

[Pantalone]

Да, ребята, программист из меня никудышный, извиняйте
ReDim Preserve нужен для того, что конечное число значений на самом деле неизвестно, 100 000 для примера тут. Неужели так ужасно по 500 прибавлять при современных объемах памяти?

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

Целочисленные это для примера, на самом деле там еще и символы имеются.

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

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

[Хакер]

ReDim Preserve нужен для того, что конечное число значение на самом деле неизвестно, 100 000 для примера тут. Неужели так ужасно по 500 прибавлять при современных объемах памяти?

Вот именно, что при современных объёмах — ужасно. Оптимальная стратегия, это каждый раз, когда не хватило места, увеличивать массив вдвое. Если для увеличения не хватило памяти — попытаться увеличит на большой блок (какое-нибудь кругле значение, типа 512/1024, а не 500). Если и эта попытка провалится — попробовать увеличить на 1. Если и это провалится — тогда сдаёмся и показываем ошибку.

А в конце подрезать излишек.

[Adam Smith]

Первая пришедшая в голову глупость:
Отсортировать список по возрастанию значений и за 1 проход посчитать кол-во вхождений каждого значения в список.
Кажется это можно сделать в ListBox'е.

Но ответа на вопрос ТС я конечно не знаю((

[Pantalone]

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

[Debugger]

Можно использовать хеш-таблицу, инкрементируя значения ячеек таблицы (и не забывая про возможные конфликты).

Если N не очень большое (~100k) - то можно завести таблицу на N элементов, пройтись сначала по исходным данным, увеличивая на единицу значения в ячейках, потом пройтись по таблице, записывая ненулевые ячейки.

Если количество уникальных элементов большое, то хеш-таблица будет неэффективна (будет много конфликтов). Тогда - отсортировать за NlogN, и потом пройтись один раз по отсортированному массиву, сравнивая следующее значение с предыдущим за N. Можно извратиться и совместить обе операции в каком-нибудь Merge Sort'e - тогда за счет выбрасывания одинаковых элементов на каждом мерже мы получим прирост в скорости. Это имеет смысл, если повторяющихся элементов может быть много (т.е. общий случай).

[Хакер]

Если не затруднит, был бы очень признателен.

Короче.

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

rnd_seq_screenshot_02.png (18.19 Кб) Просмотров: 6864

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

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

Твой код я не трогал и не улучшал вообще, за исключением того, я сделал так, чтобы все три кнопки использовали одну и ту же слуайную последовательность. Тем не менее, саму по себе случайную последовательность можно случайно задать (кнпока «Новый Seed»), так что числа по прежнему случайны, но зато во всех трёх ListView будут одинаковые результаты.

[Pantalone]

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

Попробовал так сделать, скорость работы с архивом возросла в два раза.

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

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

[Debugger]

Раз уж на то пошло:

e0006c18747094c0f05a912dfd8e0f03.png (607 байт) Просмотров: 6864

И алгоритм у меня занимает 6 строчек.

(только не надо мне говорить, что для нескольких миллионов это не прокатит. Знаю)

[Хакер]

Как-то в голове не укладывается, не вкралась ли ошибка?

Не вкралась.

Можешь сделать там кнопку, которая сравнит содержимое ListView строка за строкой. Результат будет идентичен, а мой код не использует результаты работы первых двух колонок.

[Хакер]

И алгоритм у меня занимает 6 строчек.

Этот тот же шлак, который советовал ger_kar:

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

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

Кстати, в мой код всё-таки закралась ошибка по мере копипаста. Сейчас выложу исправленную версию.

[Хакер]

Чуть подправленная версия (старая версия имела немного неверную логику вызова DoEvents, в связи с тем что я вызов вынес в конец функции, а GoSub (да, я эстет) в старом месте вставить забыл).

duplicates_for_pantalone2.zip

(22.28 Кб) Скачиваний: 183

Плюс, там ещё остался кое-какой мусор.

Там можно найти структуру ARCH_TREE_ITERATOR и пустую функцию EntryTreeIteratorInit. Я изначально хотел сделать механизм итераторов: чтобы можно было использовать некий служебный квази-объект для обхода «архива». Но в этом случае как побочный эффект строки в таблицы появились бы ещё и в отсортированном порядке (сортировка по индексу). Поскольку это пошло вразрез с задумкой сделать так, чтобы во всех трёх табличках показывался один и тот же набор случайных данных, я просто добавил поле Key в ARCH_DATA_ENTRY и сделал обход массива элементов в порядке добавления — в этом случае порядок строк во всех трёх табличках совпадает и можно искать разницу (которой нет).

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

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

[Pantalone]

Большое всем спасибо, ребята, и отдельно Хакеру. Отложил себе в запасники знаний.

[Хакер]

Отложил себе в запасники знаний.

Тогда и это отложи, рассматривиается смежный вопрос.

[ger_kar]

В примере обнаружен маленький глючек, связанный с тем, что прогресс бар не сбрасывается. И еще хотелось бы для полного понимания немого комментариев по поводу работы алгоритма. Хотя бы пояснительные наименования процедур/функций, для чего они нужны и общее словесное описание. А то что то в голове набор фрагментов, который не хочет складываться в общую картинку.

[Хакер]

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

Подтверждаю.

Хотя бы пояснительные наименования процедур/функций, для чего они нужны и общее словесное описание. А то что то в голове набор фрагментов, который не хочет складываться в общую картинку.

А что с функциями не так, они на китайском что-ли названы?

Ход мыслей был простым.

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

У него, если элементов миллион, и нужного элемента нет, приходилось каждый раз обходить массив из миллиона уже существующих. Это никуда не годится. Нам нужно увеличить производительность поиска нужного элемента в тысячи (или сотни тысяч раз). Поиск нужного элемента должен требовать не обхода миллиона элементов массива, а требовать обхода где-то примерно 10 — причём в любом (вернее худшем) случае.

Как этого можно добиться? Добиться этого можно применением древовидной структуры вместо плоского списка уже существующих элементов, как я писал:

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

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

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

Деревья бывают двоичными, бывают сбалансированными (B-дерево, B+-дерево, B*-дерево), бывают двоичными и сбалансированными (АВЛ-дерево, красно-чёрное дерево).

В моём же случае дерево ни сбалансированное, ни двоичное.

Идея состоит в том, каждая пара {ключ→значение} представлена определённым узлом в дереве. При этом в отношении индекса (будь то число или строка) определяется некое правило конвертирования самого индекса в путь-в-дереве. Способов получения пути из первоначального индекса можно придумать очень много.

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


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

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

123 — берём корневой узел, переходим к 1-му дочернему, у дочернего берём 2-й подузел, а у него самого — третью дочку, и у этого узла должно храниться значение для ключа «123».

Можно было бы придумать множество других способов, особенно для числовых индексов. Например, можно использовать байты числа, и тогда для 32-битных чисел обход дерева будет в худшем случае осуществляться за 4 шага, но у каждого узла было бы до потенциальных 256 потомков.

Можно было был использовать нибблы — 4-битные кусочки числа, и тогда ветвистость узлов составляла бы 16 ( как 2⁴). Решение с нибблами аналогично решению конверировать числовой индекс не в десятичную строчку, а в 16-ричную и использовать вместо десятичных цифр шестнадцатеричные (0—F).

Можно было было бы использовать трёх-битные кусочки числа: сдвигать биты числа влево или вправо на 3 бита, брать крайние 3 бита и использовать их, чтобы определить номер дочернего узла.

Наконец, можно было бы каждый отдельно-взятый бит числа использовать как элемент пути: в таком случае дерево превратилось бы в двоичное (у каждого узла максимум два дочерних), но это было слишком неэффективно с точки зрения расхода памяти на поддержание дерева, да и обход числа сулил бы максимум 32 шага.

Решение в качества маршрута обхода дерева использовать путь, образованный десятичными цифрами десятичного представления — не самое эффективное (использовать нибблы или байты было бы быстрее), но зато оно имеет два плюса:

• Это не так далеко от полностью текстовых ключей/индексов, то есть не придётся сильно менять код при миграции на текстовые ключи.
• Полный обход дерева позволяет получить отсортированный по ключу набор пар ключ→значение (именно в текстовой интерпретации сортировки: 1, 12, 2, 25, 34, 54, 5, 51).

Дальше — конкретика.

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

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

Так что структура узла дерева видится так: это массив указателей на дочершние узлы и указатель на собственно сами данные (если они есть для данного узла). Поскольку в VB у нас нет указателей в чистом виде (и слава богу ), вместо указателей на дочершние узлы (ноды) и указателя на данные я все ноды кладу в большой массив, и все данные кладу в большой массив, а взамен указателей на ноды и данные использую их индексы в этих массивах. При этом массивы я сознательно веду от единицы, чтобы нулевой индекс был аналогом нулевого указателя.

Поэтому вот структура для представления ноды (узла) дерева:

Код: Выделить всё

Public Type ARCH_TREE_NODE
    ChildrenIndecies()    As Long
    OwnDataEntryIndex     As Long
End Type

А вот структура для представления самого дерева (вместе с двумя массивами):

Код: Выделить всё

Public Type ARCH_TREE_OBJECT
    cNodes      As Long
    cEntries    As Long
    Nodes()     As ARCH_TREE_NODE
    Entries()   As ARCH_DATA_ENTRY
End Type


Ну и структура, отождествлющая в паре ключ—значение само значение:

Код: Выделить всё

Public Type ARCH_DATA_ENTRY
    Key             As String
    Quantity        As Long
    '
    ' Можно добавлять другие поля
    '
End Type

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

Если в дереве есть пара с ключём «123», то в дереве будет ветка \1\2\3, и конечный узел этой ветки будет иметь поле OwnDataEntryIndex, ссылающуееся на соответствующее значение. Если отдельно ключей «1» и «12» — нет, то узлы \1 и \1\2 будут иметь это поле ссылающееся вникуда (0), а если есть отдельно пары с такими ключами, то у каждой ноды поле OwnDataEntryIndex будет ссылаться на своё значение.

Если в дереве будет храниться 100 000 пар ключ—значение, то в худшем случае как минимум там будет 100 000 конечных узлов, не считая приличное число промежуточных узлов. У конечных узлов никогда не будет дочерних — именно поэтому я сделал массив индексов дочерних узлов динамическим. Пока у узла нет дочершних, массив не создан (SA-дескриптор и блок данных под элементы не размещены), и это даёт экономию памяти. К тому же, Redim массива узлов проходит легче: каждая нота это указатель на SAFEARRAY, а не сам массив, так что копирование увеличиваемого массива узлов в случае, если старый блок памяти уже некуда расширять, проходит с меньшей кровью.

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

В случае с числовым индексами корневой узел никогда не будет иметь собственных данных, но, например, при миграции на строчные индексы/ключи, если мы захотим оставить возможность в качестве ключа использовать пустую строку (""), то именно корневой узел будет своим полей OwnDataEntryIndex ссылаться на данные, ассоциированные с ключом "".

________


Собственно говоря, дальше всё вообще просто.

Я сделал функцию EntryTreeAddOrGet которая берёт дерево и нужный ключ и возвращает указатель на данные, ассоциированные с этим ключом, ссылку на ARCH_DATA_ENTRY, ассоциированный с этим ключом.

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

Ключ в путь генерируется функцией InitPathElms. Дальше идёт обход.

Обход начинается с корневого узла:
iCurNode = 1 ' Начинаем с корневого узла

итеративно, до того момента, пока не пройдём через весь путь (не достигнем конца пути):
Loop Until iPathElm = cPathElms

На каждой итерации мы смотрим в таблицу дочерних элементов:

Код: Выделить всё

            On Error GoTo AllocateChildrenList
            iNextNode = .Nodes(iCurNode).ChildrenIndecies(PathElms(iPathElm))
            On Error GoTo 0

(которая, если её нет, создаётся при первом обращении)

И если в ней ссылка на соответствующий дочершний узел не установлена (то есть узла нет), то дочершний узел создаётся:

Код: Выделить всё

            If iNextNode = 0 Then
                iNextNode = EntryTreeAllocateNode(tree, iCurNode, PathElms(iPathElm))
            End If
           

И этот дочершний узел становится новым текущим:
iCurNode = iNextNode
а мы двигаемся к следующему шагу маршрута (пути):
iPathElm = iPathElm + 1

И это всё повторяется до тех пор, пока нам есть куда идти далше, то есть пока остались шаги в «маршрутном листе»:
Loop Until iPathElm = cPathElms

Когда весь путь (от корневого узла до текущего) пройден, текущий узел объявляется конечным.

И если в с конечным узлом уже были ассоциированы какие-то данные, то возвращается их индекс:

Код: Выделить всё

        If .Nodes(iCurNode).OwnDataEntryIndex <> 0 Then
            EntryTreeAddOrGet = .Nodes(iCurNode).OwnDataEntryIndex

А если не были (узел был создан только что), то создаётся соответствующая структура ARCH_DATA_ENTRY и, опять таки, возвращается её индекс:

Код: Выделить всё

        Else
            EntryTreeAddOrGet = EntryTreeAllocateEntry(tree, iCurNode, sIndexInternal)
        End If

Вот и всё.

Для миграции на текстовые индексы надо переделать InitPathElms и поменять код создания массива дочершних узлов:
ReDim tree.Nodes(iCurNode).ChildrenIndecies(0 To 9)

[Pantalone]

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

[hclubmk]

Это пять! Отличное и решение и объяснение!