|
Тестирование разных контейнеров и другая болтовня
|
|
| haav | Дата: Воскресенье, 16.01.2022, 19:58 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Сюда перенес обсуждение отсюда
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 19:58 | Сообщение # 2 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Посмотрел по сети несколько реализаций хештаблиц. Но все они какие-то тормозные. Может мне не повезло и есть реально крутые... Авторы IUP написали довольно быструю реализацию. Хотя конечно glib в 2.5 раза быстрее. Но для IUP реализации не нужно тащить с собой DLL как для glib под винду. Я для себя вытащил iup hashtable в отдельную статическую либу (мало ли нужно будет что-то сделать с помощью хештаблиц , а подключать всю библиотеку IUP не всегда бывает нужно). В общем , годная вещь.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 19:58 | Сообщение # 3 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Поторопился я нахваливать 
В общем , чудес среди простых смертных не бывает. И скорость в данном случае достигается банально из-за того , что строки не сравниваются , а используется для проверки хеш.
Поясню:
хеш для проверки в данном случае сомнительная штука , поскольку могут нередко возникать коллизии. И скорость будет достигаться за счет багов. Вот например:
Код #include Once "iup_table.bi"
Dim tbl As Itable Ptr = iupTableCreate(IUPTABLE_STRINGINDEXED)
iupTableSet(tbl, "as" , Cast(Any Ptr , @"str1") , IUPTABLE_STRING)
iupTableSet(tbl, "bT" , Cast(Any Ptr , @"str2") , IUPTABLE_STRING)
? *Cast(Zstring Ptr , iupTableGet(tbl, "as"))
? *Cast(Zstring Ptr , iupTableGet(tbl, "bT"))
iupTableDestroy(tbl)
Вы не получите строку "str1" по ключу "as" , потому что хеш у них одинаковый. Такой же хеш и у ключа "c5". В общем быстро , но ненадежно. У функции iupTableCreate можно задать другой параметр , но там сохраняются только указатели. Так что, не все так радостно.
И с glib как оказалось нет никакого волшебства. Просто я подсунул удобный пример, где в основе хеша лежит указатель на строку. Конечно же указатели уникальны, поэтому и распределение по таблице равномерное, отсюда и скорость. Но для этого надо чтобы указатель не менялся. А значит далеко не для всех ситуаций такое сгодится.
Я почти дописал свой вариант. Я конечно надежность буду ставить на первый план , а уж скорость как получится.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| WQ | Дата: Воскресенье, 16.01.2022, 19:59 | Сообщение # 4 |
|
Полковник
Группа: Проверенные
Сообщений: 215
Статус: Offline
| haav
Интересно, при более длинных ключах количество коллизий будет падать?
А вообще, конечно, не очень хорошо
На англоязычном форму встречался пример:
https://www.freebasic.net/forum....p211105
Потестировал - вроде тоже иногда перевирает данные
А я пытаюсь перевести на freebasic примеры такого типа данных, как строп или "веревка"
https://ru.wikipedia.org/wiki....%D1%85)
Довольно интересная вещь, позволяет работать со строками в десятки миллионов символов
Проблема с адаптацией для произвольных типов данных
Сообщение отредактировал WQ - Среда, 12.01.2022, 23:23 |
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 19:59 | Сообщение # 5 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата WQ (  ) Интересно, при более длинных ключах количество коллизий будет падать?
Наоборот. Больше символов - больше коллизий. Пока строка ключа при обработке будет помещаться в тип хеша , кол-во коллизий с каждым символом будет расти приблизительно в 3 раза. При переполнении типа хеша даже не берусь судить , но думаю там может быть как небольшое кол-во , так и лавинообразный всплеск.
Цитата WQ ( ) Потестировал - вроде тоже иногда перевирает данные
Если там тот же принцип проверки не по точному сравнению строк , а по хешу - тогда следует ожидать неприятностей.
Цитата WQ ( ) А я пытаюсь перевести на freebasic примеры такого типа данных, как строп или "веревка" https://ru.wikipedia.org/wiki....%D1%85)Довольно интересная вещь, позволяет работать со строками в десятки миллионов символов Проблема с адаптацией для произвольных типов данных
Не ожидай , что это будет космический вариант. Ведь это по сути то же бинарное дерево , а значит даже в лучшем варианте скорость будет O(log n).
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 19:59 | Сообщение # 6 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| @WQ
Если хочешь , можешь попробовать реализацию моей таблички: https://users.freebasic-portal.de/freebasicru/hash_table.html
Кстати провел некоторые результаты тестирования. 2 теста.
1) просто загонял строки от 1 до 200000
результаты в секундах:
хеш таблица - 0.23
связанный список - 200 (полный ахтунг)
сбалансированное дерево - 1.1
бинарное дерево - 0.68
2) различные строки длиной от 10 до 60 символов , всего строк 61380
хеш таблица - 0.093
связанный список - 14.5
сбалансированное дерево - 0.32
бинарное дерево - 11.4
Как видно в обоих тестах хеш таблица в лидерах. Бинарное дерево в первом тесте сумело обогнать сбалансированное , но это просто данные оказались слишком удобные. Второй тест сразу поставил все по местам. Бинарное дерево оказалось почти полностью вырожденным (превратилось почти в связанный список). Ну и конечно связанный список ожидаемо аутсайдер. Так что я доволен табличкой.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 19:59 | Сообщение # 7 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Со временем добавлю табличку в проект контейнеры , пусть все будет в одном месте.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| WQ | Дата: Воскресенье, 16.01.2022, 19:59 | Сообщение # 8 |
|
Полковник
Группа: Проверенные
Сообщений: 215
Статус: Offline
| Цитата haav ( )
Цитата haav ( ) Не ожидай , что это будет космический вариант. Ведь это по сути то же бинарное дерево , а значит даже в лучшем варианте скорость будет O(log n).
Это не для замены хэш-таблицы, а для работы, по сути, с 1 "строкой", но очень длинной - основа текстового редактора, быстрая вставка\удаление больших последовательностей элементов -"символов"
Использование массивов, векторов, списков и т.д. неэффективно в таком случае
Вообще, массив из freebasic довольно неплох
Например, у меня выходило, что доступ к элементу хэш-таблицы IUP в 100 раз медленнее, чем доступ к элементу массива
То есть при количестве элементов до нескольких сотен просто перебор будет проще при той же скорости и не потребует дополнительного большого кода
Когда создавал для IUP элемент-список (аналог listbox), как основную структуры хранения данных списка проще всего оказалось использовать массив.
Смотрел вектор из Containers (старый вариант), множество разных списков, деревьев - все слишком медленные, особенно на этапе создания\заполнения элементами. Плюс сложности с управлением памятью, сортировка и т.п.
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 19:59 | Сообщение # 9 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата WQ ( ) Вообще, массив из freebasic довольно неплох
Например, у меня выходило, что доступ к элементу хэш-таблицы IUP в 100 раз медленнее, чем доступ к элементу массива
То есть при количестве элементов до нескольких сотен просто перебор будет проще при той же скорости и не потребует дополнительного большого кода
Конечно же для нескольких сотен не надо ничего изобретать. Контейнеры типа деревьев, хеш таблиц, списков больше нужны для оперирования большими неопределенными заранее объемами данных. И все зависит от задачи. Никогда не получится создать что-то быстрое и пригодное для любых задач. Для частных решений нередко приходится создавать что-то одноразовое.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 20:00 | Сообщение # 10 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Я обновил сборник контейнеров. Кстати , теперь справка в архиве на русском.
если что, ссылки на контейнеры:
https://sourceforge.net/projects/freebasic-containers/files/
https://users.freebasic-portal.de/freebasicru/download.html#containers
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 20:00 | Сообщение # 11 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Цитата WQ ( )
Провел тесты этой реализации. Она в 3 раза медленнее моей. Попробовал заменить ей хеш функцию , стало чуть быстрее , но почти не повлияло на результат. Похоже там сам алгоритм заполнения\получения медленный. А если , как ты говоришь, она еще и врет , то результат неуд.
Есть еще одна реализация от paul doe: https://www.freebasic.net/forum/viewtopic.php?f=7&t=31378 , но там столько макросов , что без пол литра не разберешься. Надо спросить у самого автора , как сделать простой пример с ключом и данными , чтобы протестировать.
Попробовал map из purebasic:
Код StartTime.q = ElapsedMilliseconds()
NewMap Country.s()
For i = 0 To 200000
Country(Str(i)) = Str(i)
Next
For i = 0 To 200000
If FindMapElement(Country(), Str(i))
w.s = Country()
EndIf
Next
MessageRequester("", Str(ElapsedMilliseconds() - StartTime))
Отладчик на время тестирования конечно отключил.
Результат: 2.1
То есть в 2 раза медленнее моей реализации сбалансированного дерева (map из контейнеров) и почти в 10 раз медленнее моей хеш таблицы. В общем пуребейсиковский мэп на троечку с минусом  .
Кстати purebasic под linux - вообще какой-то стремный. Открыл справку , пытаюсь оттуда перетащить пример - не работает. Пытаюсь скопировать с помощью CTRL+C - не работает. Контекстное меню с пунктом копирования не существует. Пришлось открывать свой редактор , перетаскивать текст туда и уже оттуда копировать через клавиши в окно purebasic редактора. Когда открываешь плюсик в справке (чтобы раскрыть дерево) , фокус постоянно куда-то улетает. В редакторе всплывающее окно с автодополнением не отзывается ни на какую кнопку , только на клик мыши и при окне автодополнения полностью блокируется ввод в редактор. Если бы я писал в этой среде , то отключил бы начисто эту функцию - потому что так работать невозможно. Блин за такое еще и деньги берут. Еще под винду редактором и справкой пользоваться более менее, но под linux непригодно.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| zamabuvaraeu | Дата: Воскресенье, 16.01.2022, 20:00 | Сообщение # 12 |
|
Подполковник
Группа: Друзья
Сообщений: 149
Статус: Offline
| От пуребасикистов мне постоянно прилетает: «Да у тебя даже IDE нет» или «запустил фреебасик, открылось какое‐то DOS окно, как тут кодить?!?!?!»
Я так понимаю, они очень гордятся своей IDE, например, умеет раскрашивать ключевые слова. Однако подсветку синтаксиса умеет делать даже Far Manager и Notepad++.
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 20:00 | Сообщение # 13 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Провел еще одно тестирование. Система Linux 64-bit
Кол-во ожидаемых элементов для заполнения и последующего поиска 43352064
Длина ключа всегда 4 , длина данных от 1 до 6 символов
делал перебором в 4 вложенных циклах
Моя хеш таблица
расход памяти: 4.38GB
время работы: 499 секунд
выполнена работа на 100% (100% заполнение и 100% поиска)
Моя реализация MAP (на основе сбалансированного дерева)
расход памяти: 5.11GB
время работы: 307.9 секунд
выполнена работа на 100% (100% заполнение и 100% поиска)
Таблица paul doe
расход памяти: 9.9GB
время работы: 1540 секунд
выполнена работа на ~63% (100% заполнение и 25% поиска , дальше ждать надоело)
Purebasic (отладчик отключен)
память писать бессмысленно , поскольку невозможно даже дождаться заполнения
время работы: 1230
выполнена работа только на ~7% (~15% заполнение , дальше ждать надоело , быстрее солнце потухнет)
Итог:
1) Удивительно , но в данном случае победила именная реализация MAP на основе сбалансированного дерева , хотя по расходу памяти превысило таблицу.
2) Моя хеш таблица заняла 2 место
2) Таблица paul doe много жрет памяти и медленная. Данные не теряет , проверял.
3) MAP из PureBasic просто неприемлемо , даже не ожидал , что это такое дерьмо.
А теперь исходные коды:
1) пример с использованием моего MAP:
Код #include once "MAP.bi"
var t = timer
MMAPTemplate(string , string)
Dim As TMAPstringstring Ptr pTable = New TMAPstringstring
dim q as Long = 0
for i1 as Long = 32 to 80
for i2 as Long = 32 to 127
for i3 as Long = 32 to 127
for i4 as Long = 32 to 127
dim as string ss = chr(i1) & chr(i2) & chr(i3) & chr(i4)
pTable->insert(ss , str(q))
q+=1
Next
Next
Next
? "loop="; i1 , q
Next
? "filled" , q
q = 0
for i1 as Long = 32 to 80
for i2 as Long = 32 to 127
for i3 as Long = 32 to 127
for i4 as Long = 32 to 127
dim as string ss = chr(i1) & chr(i2) & chr(i3) & chr(i4)
var w = pTable->find(ss)
q+=1
Next
Next
Next
? "loop="; i1
Next
? timer -t
2) пример с использованием моей HashTable:
Код #include once "HashTable.bi"
var t = timer
MHashTemplate(Zstring , Zstring)
Dim As THASHTABLEzstringzstring Ptr pTable = New THASHTABLEzstringzstring
dim q as Long = 0
for i1 as Long = 32 to 80
for i2 as Long = 32 to 127
for i3 as Long = 32 to 127
for i4 as Long = 32 to 127
dim as string ss = chr(i1) & chr(i2) & chr(i3) & chr(i4)
pTable->insert(ss , str(q))
q+=1
Next
Next
Next
? "loop="; i1 , q
Next
? "filled" , q
q = 0
for i1 as Long = 32 to 80
for i2 as Long = 32 to 127
for i3 as Long = 32 to 127
for i4 as Long = 32 to 127
dim as string ss = chr(i1) & chr(i2) & chr(i3) & chr(i4)
var w = pTable->find(ss)
q+=1
Next
Next
Next
? "loop="; i1
Next
? timer -t
3) пример с использованием таблицы paul doe:
Код #include once "inc/collections.bi"
var t = timer
template( Dictionary, of( string ), of( string ) )
dim q as Long = 0
var d = Dictionary( of( string ), of( string ) )
for i1 as Long = 32 to 80
for i2 as Long = 32 to 127
for i3 as Long = 32 to 127
for i4 as Long = 32 to 127
dim as string ss = chr(i1) & chr(i2) & chr(i3) & chr(i4)
d.add( ss, new string( str(q) ) )
q+=1
Next
Next
Next
? "loop="; i1
Next
? "filled"
q = 0
for i1 as Long = 32 to 80
for i2 as Long = 32 to 127
for i3 as Long = 32 to 127
for i4 as Long = 32 to 127
dim as string ss = chr(i1) & chr(i2) & chr(i3) & chr(i4)
var s = d[ ss ]
q+=1
Next
Next
Next
? "loop="; i1
Next
? timer -t
4) Пример PureBasic MAP:
Код OpenConsole()
StartTime.q = ElapsedMilliseconds()
NewMap Country.s()
q.i = 0
For i1 = 32 To 80
For i2 = 32 To 127
For i3 = 32 To 127
For i4 = 32 To 127
ss.s = Chr(i1) + Chr(i2) + Chr(i3) + Chr(i4)
Country(ss) = Str(i)
q+1
Next
Next
Next
Print("filled" + Str(i1) + " " + q)
Next
q = 0
For i1 = 32 To 80
For i2 = 32 To 127
For i3 = 32 To 127
For i4 = 32 To 127
ss.s = Chr(i1) + Chr(i2) + Chr(i3) + Chr(i4)
If FindMapElement(Country(), ss)
w.s = Country()
EndIf
q+1
Next
Next
Next
Print(Str(i1))
Next
Print(Str(ElapsedMilliseconds() - StartTime))
; IDE Options = PureBasic 5.73 LTS (Linux - x64)
; CursorPosition = 27
; FirstLine = 17
; EnableXP
; Executable = 12222
; DisableDebugger
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 20:00 | Сообщение # 14 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Странное дело , когда запустил их PureBasic редактор во второй раз , автодополнение стало работать по клавише TAB и копирование из справки с помощью CTRL+C заработало. Чудеса , да и только.
Цитата zamabuvaraeu ( ) От пуребасикистов мне постоянно прилетает: «Да у тебя даже IDE нет» или «запустил фреебасик, открылось какое‐то DOS окно, как тут кодить?!?!?!»Я так понимаю, они очень гордятся своей IDE, например, умеет раскрашивать ключевые слова. Однако подсветку синтаксиса умеет делать даже Far Manager и Notepad++.
Так они все в основном пользователи винды (включая автора пурика?) , а на винде таких косяков нет. И я так и не понял , как воткнуть в их редактор терминал. Вот запускаю я из IDE приложение с консольными командами OpenConsole , Print , и пр. , а в ответ тишина. Приложение висит в процессах , но окна терминала нет. Конечно я могу его скомпилировать и потом отдельно запустить в терминале. Но в чем тогда смысл их IDE? Платный продукт , а такой необходимой вещи для linux сделать не смогли.
Добавлено позже:
Опять запустил их редактор и опять копирование из справки не работает. Че за хрень...
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
| haav | Дата: Воскресенье, 16.01.2022, 21:07 | Сообщение # 15 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 1373
Статус: Offline
| Вот связанный список на пурике выше всяких похвал , рвет в пух и прах любую мою реализацию связанного списка. Разница аж в 4 раза при заполнении 1000000 элементов. Как удалось добиться такой скорости х.з.
Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
|
| |
| |
|
