Аналог ассоциативного массива

[AZJIO]

Так выкладок то не было... Даже логического объяснения видения в чём может быть ускорение по сравнению с моим логическим объяснением. Кроме объяснения что люди умные есть уже далеко продвинулись.

 

[Oki]

с моим логическим объяснением

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

Насколько я понимаю в общих чертах, при добавлении элементов в ассоциативный массив экономичные по времени выполнения алгоритмы на ходу строят способ вычисления адреса, по которому должен находиться любой существующий ключ, по содержанию ключа. Вычисление заканчивается успехом для существующих ключей и отказом для новых. Способ вычисления подстраивается по ходу добавления элементов, так что к любому моменту поиска вся необходимая структура готова для использования. Кажется невероятным существование такого математического аппарата? Так подобных "невероятных" случаев в истории было предостаточно.

 

[Prog]

А наоборот можно делать? То есть создавать dll из AutoIt-скрипта

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

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

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

 

[Oki]

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

Это так называемый упорядоченный ассоциативный массив, сложность алгоритма поиска в нём, конечно, всего лишь O(log n), что куда меньше единственно возможного в рассуждениях уважаемого AZJIO, но всё же ещё далека от O(1), достижимого в оптимальных алгоритмах.

 

[Prog]

Я в целом в процессе принятия решения отказываться делать подобную работу на AutoIt.

AutoIt для несложных автоматизаций и работе с COM. Это у него хорошо это получается. В остальном, многие задачи намного проще решать на других ЯП.

 

[AZJIO]

отсортирован

Я ведь эту тему тоже затронул. Чтобы отсортировать список понадобиться куда больше ходов, чем при не сортированном списке. Если в первом случае мы сверяем с первым символом первый символ искомого и сразу определяем за один шаг возможный кандидат на дубликат, то при сортировке любой элемент списка не гарантированно передвинется за 1 раз в нужную позицию. Именно поэтому я и упомянул про вариант создания структурного дерева, где упомянул про 16 элементов в первом родительском ряду, где 16 для md5, потому что 16 символов в md5 (0-9, A-F), а если брать произвольные строки, то рассматривать их бинарно по байтам, так как известно что наибольшая скорость считывания данных за один шаг байтами, а значит пока отбрасываем возможность без учёта регистра и сравниваем байты (0-256 или 0 - FF). Построение такого дерева будет требовать мегафлопсы больше чем непосредственное сравнение, хотя надо тестить, возможно этот алгоритм начнёт работать быстрее при более миллиона элементов, так как начнётся перевес, когда добавление очередного элемента в одном случае потребует сравнения с первым символом более миллиона элементов, во втором случае сравнение со структурой, в кокторой в первом ряду будет меньше миллиона элементов, по числу символов или для байтов это равно 256. Если символ 2 байта то получается 65536, но это при условии что в первом символе задействованы все символы, а так как это не так, а например руский, английский и числа, то 33+26+10 получаем 69, то есть за 69 шагов мы определим сравнение для первого символа элемента, а при сравнении с миллионным списком потребуется миллион шагов. То есть получается сравнение и добавление элемента технически требует встраивание в структурное дерево, а также при чтении такого дерева надо формировать обратный процесс, ну или для каждого последнего элемента дерева хранить указатель на структуру, где будет находится строка в первозданном виде и счётчик дубликатов. То есть надо технически измерять для какого числа элементов и для какой средней длины элементов такой способ будет работать быстрее. Допустим если сравнивать скорость цикла с примитивным условием, то миллион раз отрабатывает мгновенно, то есть на самом деле даже сравнение миллион раз может оказаться продуктивней чем построение дерева.

Сообщение автоматически объединено: 5 Июл 2022

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

карта в PureBasic и Scripting.Dictionary на ходу строят адреса кключей, а любой символ строки, так же легко вычисляется от адреса строки плюс число сдвига и получаем любой символ. Но тогда надо знать длину строки, чтобы не выйти за пределы, а для измерения длинны строки надо пробежаться до null-символа, либо на этапе построения данных (собственная карта) при поиске переноса строк то есть получения указателей сразу сохранять длины.


.

 

[Prog]

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

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