ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
25 сообщений из 227, страница 8 из 10
  8  все
Тяпничная унификация
    #39519423
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Dima T,

Нет смысла брать два разных хэша, если можно сразу взять один суммарной длины. Я так понимаю, что математически - хуже во много мульенов раз (что то типа разницы между суммой величин и произведением).
...
Рейтинг: 0 / 0
11.09.2017, 18:23
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519457
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SiemarglDima T,

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

Там экономия на размере биткарты: или два хэша по 32 бита в одной биткарте на 32 бита, или вместе в одной на 64 бита.
...
Рейтинг: 0 / 0
11.09.2017, 19:13
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519501
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonХм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.
Код: plaintext
1.
2.
c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status


gcc version 6.3.0 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)
Посмотри psapi.h есть там объявление GetProcessMemoryInfo() ?
Может он в какие-нибудь #if обернут, тогда может какой-то #define надо объявить.
Привет. Только дополз до ноутбука. Завал по проекту. ОК. Посмотрю.
Надо студию поставить. Последний раз я качал 2005 году Express Ed.
Что щас там чо и как у большого брата?
...
Рейтинг: 0 / 0
11.09.2017, 21:48
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519511
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonНадо попробовать BloomFilter. Он более эффективно заполнит эту пустоту. И на размере сэкономить можно.
С полноценным фильтром Блума ерунда получается.
ВикиОбычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом
В нашем случае непонятно как это использовать.

Я кажется понял твое негодование. Ты хочешь решить задачу в 1 проход? Мне кажется
какие-бы алгоритмы и структуры мы не применяли но встает такая аксиома.

Если не сохранять ключи на 1-м проходе то второй проход будет как минимум
необходим для отчота

По поводу Блума (BF) чорт бы его подрал. Эта структура - вспомогательная. Ее обычно
ставят в каскад к основной структуре. Например к диску. Быстро отбивать "дурные"
негативные реквесты на isExist(string key). Я бы - вставил ее в цепочку с LRU (на 100 ключей хотяб)
и можно читать основной файл. Примерно как в алгоритме Зямы. (Насколько я его понял).

По поводу экономии места. Я щас навскидку не помню. Чуть позже я опубликую
блог своей борьбы со Слоном. Тоесть с Хадупом. Там я разбирал работу встроенного
BF в слона и был очень разочарован удобством API. Специально потом лазил в вики
чтоб понять какие там нужны аргументы к коснтруктору чтоб контролировать ситуацию
полностью. Вобщем слушай телегу.

BF может работать на любом объеме биткарт. Его можно впихнуть в 256Мб и в 128 и в 64.
Он очень толерантен к размеру. В этом его главное преимущество. За размер мы заплатим
свою цену. Это false-positive срабатывания которые мы всё равно решаем за счет второго
прохода. Формулу достоверности в % я предоставить не могу но у меня есть свой численный
метод который даёт табличку аспектов таких как
- размер биткарты
- количество ключей которые мы хотим положить
- % false-positive срабатываний (обычно берут 3-5%)
- количество хеш-функций.
Все 4 аспекта связаны формулой. Если двигаешь что-то одно - то меняется другое. Это уравнение
с 3 неизвестными долго вгоняло меня в ступор пока я не решил просто зафиксировать 2 из
трех неизвестных и уравнение решилось.

Что произойдет если BF заполнять количеством ключей гораздо больше чем было расчитано?
Ничего страшного. Он так-же будет работать. Тянется как резиновый. Вот только свойства
false-positive у него ухудшатся.

Экпериментально я установил что BF заполненный на 100% оценочным числом ключей
содежит в себе одинаковое количество включенных и выключенных бит. Тоесть он
шумит битами в соотношении 50%. Красиво шумит. Криптографически красиво.

Вот почему меня вдруг заинтересовало (по топику выше) насколько плотно мы используем
карту CRC-32. И я вспомнил свою борьбу со Слоном.

Какая польза от BF в наших разработках? Он сэкономит место для других полезных структур данных
в оперативке. Вот пожалуй всё.
...
Рейтинг: 0 / 0
11.09.2017, 22:14
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519512
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Siemargl, привет бро. Пофикси plz то что у тебя закомментарено.
...
Рейтинг: 0 / 0
11.09.2017, 22:16
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519562
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
maytonSiemargl, привет бро. Пофикси plz то что у тебя закомментарено.В связи с отсутствием валидных входных данных, моя гениальная программа не требует фиксов.

Собственно, я об этом уже писал. 20783791

Кстати см, что модеры похерили ваши хакерские БД
...
Рейтинг: 0 / 0
11.09.2017, 23:22
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519563
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это я удалил. Не compliance по отношению к правилам
форума. Но в личку могу дать ссылки.
...
Рейтинг: 0 / 0
11.09.2017, 23:25
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519613
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНадо студию поставить. Последний раз я качал 2005 году Express Ed.
Что щас там чо и как у большого брата?
У меня стоит бесплатная Visual Studio Community 2015 .
Есть 2017 , ее не пробовал ставить.

В целом подтянулись, стандарты С++11 и 14 поддерживает. Но в С отсебятина так и осталась.
...
Рейтинг: 0 / 0
12.09.2017, 07:04
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519628
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЯ кажется понял твое негодование. Ты хочешь решить задачу в 1 проход? Мне кажется
какие-бы алгоритмы и структуры мы не применяли но встает такая аксиома.

Если не сохранять ключи на 1-м проходе то второй проход будет как минимум
необходим для отчота
В 1-й проход я получаю 100% ключей с уникальным хэшем и по каким из них были повторы или коллизии. Или 100% уникальных хэшей. Дальше мне остается проверять только те ключи, по которым были повторы хэша. И проверять только в подмножестве уже найденных, а не во всех найденных. Т.е. хэш это вспомогательный ID для поиска того что надо допроверять. После первого прохода биткарта в найденными уникальными удаляется из памяти. В общем на первой биткарте нельзя использовать Блума.

Пока писал, понял: на второй биткарте (где хранятся хэши повторов) можно использовать Блума, т.к. не смертельно если на втором проходе я перепроверю 3-5% ранее найденных уникальных. Зато можно значительно уменьшить биткарту с 512 Мб до 128/64 Мб, а освободившуюся память более эффективно использовать.

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

PS В камментах описал алгоритм, но забыл поправить описаловку после изменения. Поправлю.
...
Рейтинг: 0 / 0
12.09.2017, 08:01
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39519879
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЭто я удалил. Не compliance по отношению к правилам
форума. Но в личку могу дать ссылки.
Я тот файлик глянул на предмет что за длинные строки там
 
Начало самой длинной (422894 байта)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
$HEX[706d6a5883807daadee0ddf3f3f6f4fef7f8f8fffcfdfdfffafafafff8f7f6fee6e4e2f383807daa706d6a580000000
906060602ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00fefefe01fbfbfb04f7f7f708f6f6f609ededed12bec0be58b5bab7cbffffffffced
dd3ffc3d5cbffd8e2ddffe8ebeafff0ededffecdcd7fff1e1dbffffffffffbdc2becec0c3c159f6f6f609ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff002b2b2b010101010643413f1a73706d5f7e7b778d827f7ca585827eb3827f7ca57e7b778d73706d5
f43413f1a010101062b2b2b01ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f70
0f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f
7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f70
0f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f
7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f70
0f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700f7f7f700ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
02b2b2b010101010643413f1a73706d5f7e7b778d827f7ca585827eb3827f7ca57e7b778d73706d5f43413f1a010101062b2
b2b01ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
fff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff0
0ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00ffffff00fff
...

ИМХО Троян какой-то текстовый. Что бы это могло означать?
...
Рейтинг: 0 / 0
12.09.2017, 14:09
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520072
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Понятия не имею что там.

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

Был вариант сгенерить их. Но этот вариант был:
- не убедителен
- не имел хорошей энтропии

И я решил просто искать в открытых источниках справочники и выгрузки БД
...
Рейтинг: 0 / 0
12.09.2017, 19:27
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520078
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Список аннулированных паспортов Легально и много (105 млн. записей).

Если покопаться в открытых данных , то там много полезного для наших тестов найдется.
...
Рейтинг: 0 / 0
12.09.2017, 19:48
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520106
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonХм... после того как ты добавил win-функции я перестал успешно собирать твой исходник.
Код: plaintext
1.
2.
c:\tmp\ccwjaIPM.o:uniq-crc.cpp:(.text+0x347): undefined reference to `GetProcessMemoryInfo'
collect2.exe: error: ld returned 1 exit status


gcc version 6.3.0 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)
Посмотри psapi.h есть там объявление GetProcessMemoryInfo() ?
Может он в какие-нибудь #if обернут, тогда может какой-то #define надо объявить.
Посмотрел. Норм. Есть. Не обернут ни во что.

Код: plaintext
1.
  WINBOOL WINAPI GetProcessMemoryInfo(HANDLE Process,PPROCESS_MEMORY_COUNTERS ppsmemCounters,DWORD cb);
...
Рейтинг: 0 / 0
12.09.2017, 20:56
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520114
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T Список аннулированных паспортов Легально и много (105 млн. записей).

Если покопаться в открытых данных , то там много полезного для наших тестов найдется.
Спасибо. Качнул паспорта. Добавлю в тестовые выборки.
...
Рейтинг: 0 / 0
12.09.2017, 21:36
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520119
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
 
NameFile LengthRowsDamaged RowsCardinalityAvg RLMedian RL75-perc RL97-perc RLMax RLc:\db\1.2billion\1.2billion.lst13 GB120677026301010121863c:\db\anti-spam\dom-bl-base.lst3 MB22800601616202867c:\db\anti-spam\dom-bl.lst13 KB77201616192733c:\db\anti-spam\from-bl.lst4 MB16811602828314071c:\db\CDDB\edit.lst4 GB438916800109112117118119c:\db\CDDB\edit_area.lst13 MB92867701314141415c:\db\CDDB\edit_artist.lst885 MB5370593701617171718c:\db\CDDB\edit_data.lst27 GB438906351045656428586298765502c:\db\CDDB\edit_event.lst3 MB23562201313131314c:\db\CDDB\edit_instrument.lst15 MB130516001111111112c:\db\CDDB\edit_label.lst32 MB210772801515161617c:\db\CDDB\edit_note.lst3 GB26856966215411417449051183c:\db\CDDB\edit_note_recipient.lst32 MB232297401314141516c:\db\CDDB\edit_place.lst11 MB81403301313131314c:\db\CDDB\edit_recording.lst906 MB5590619101615161617c:\db\CDDB\edit_release.lst365 MB2361387101515151516c:\db\CDDB\edit_release_group.lst256 MB1634517501515151516c:\db\CDDB\edit_series.lst1 MB11991801212121213c:\db\CDDB\edit_url.lst82 MB517968501515151516c:\db\CDDB\edit_work.lst109 MB648825601616161617c:\db\HashKiller\hashkiller-dict.lst1 GB8840540921129124155224c:\db\Linked-In\SHA1.lst240 MB6143150040-1-1-140c:\db\Psyc\AllMain_aA4_eE3_gG6_lL1_oO0__sS5_tT7.lst5 GB549682416099101431c:\db\Psyc\CommonPassword_aA4_eE3_bB8_gG6_lL1_oO0_zZ2_sS5_tT7.lst3 GB39085521308881115c:\db\Psyc\ComputerJargonLower+4PrefixWPA.lst1 GB8954436901212141935c:\db\Psyc\FamilyNamesLower+4PrefixWPA.lst1 GB13070572801011121521c:\db\Psyc\FemaleNamesLower+4PrefixWPA.lst1011 MB9527654801010111319c:\db\Psyc\JunkLower+4PrefixWPAFull.lst1 GB8693605301111131727c:\db\Psyc\MaleNamesLower+4PrefixWPA.lst662 MB633379650910111319c:\db\Psyc\MovieNamesLower+4PrefixWPAFull.lst161 MB1319800701112131620c:\db\ripe\ripe.lst5 GB1434106040373644828662c:\db\passports\list_of_expired_passports.csv1 GB10948187401011111125
...
Рейтинг: 0 / 0
12.09.2017, 21:57
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520198
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima Tпропущено...

Посмотри psapi.h есть там объявление GetProcessMemoryInfo() ?
Может он в какие-нибудь #if обернут, тогда может какой-то #define надо объявить.
Посмотрел. Норм. Есть. Не обернут ни во что.

Код: plaintext
1.
  WINBOOL WINAPI GetProcessMemoryInfo(HANDLE Process,PPROCESS_MEMORY_COUNTERS ppsmemCounters,DWORD cb);


Тогда непонятно что ему не нравится.

На всякий случай залил свежий exe в zip, пароль 12345.
...
Рейтинг: 0 / 0
13.09.2017, 08:00
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520691
Bred eFeM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bred eFeM
Участник
Дайте данных )

Собрал однопроходный (держим все строки в памяти) черновик.
Потоптал пенопласт - проверил, работает ли идея растасовки строк и быстрого отсева копий.
Вроде получилось, теперь есть идеи распараллелить...

P.S.
"Девять миллиардов имён Бога"
...
Рейтинг: 0 / 0
13.09.2017, 19:05
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520695
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Bred eFeMДайте данных )
Качай Список аннулированных паспортов .

Для ужесточения сделай
Код: plaintext
1.
copy passport.csv + passport.csv crash-test.csv
...
Рейтинг: 0 / 0
13.09.2017, 19:21
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520710
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Bred eFeMВроде получилось, теперь есть идеи распараллелить...
Откомпилируй в x86 для начала. Если отработает - параллель.
...
Рейтинг: 0 / 0
13.09.2017, 19:47
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520725
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Друзья. По поводу параллелизма. Не спешите. Данный алгоритм - последовательный
по своей природе. Если у вас дисковое хранилище на базе RAID-0 то пробуйте. Но
нам будет очень сложно обобщить ваши результаты на обычные конфигурации.

Во всех остальных случаях (рабочая станция + 1 физический диск) - не заморачивайтесь!
Не тратьте время на ерунду! У вас узким местом будет канал дисковой подсистемы
и ничего вы там не распараллелите.

Подумайте над алгоритмом.
...
Рейтинг: 0 / 0
13.09.2017, 20:30
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520731
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Bred eFeMДайте данных )

Собрал однопроходный (держим все строки в памяти) черновик.
Потоптал пенопласт - проверил, работает ли идея растасовки строк и быстрого отсева копий.
Вроде получилось, теперь есть идеи распараллелить...

P.S.
"Девять миллиардов имён Бога"
Ты брутфорсишь наш первый вариант который Naive Hash-table(NHT) ?
Посмотри исходник Димы под названием uniq-mem.

Еще. Если у тебя есть оригинальная идея. Мы имеем общий репозитарий. Регайся в sourceforge.

По поводу имен Бога. Это дежа-вю... Тяпничный pwdgen
...
Рейтинг: 0 / 0
13.09.2017, 20:39
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520791
Bred eFeM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bred eFeM
Участник
Dima Tкачай список- ужо, это я из-за него и психанул - как оказалось там 7 раз одно и то же в кучу слито.
- ну и строки одинаковой длины - хороший тест.
Откомпилируй в x86 для началапопробую, но особо смысла не вижу - по использованию памяти должно работать: динамично до 512М для строк не более 4 символов + динамично до 64М под структуру + рабочих 128М + rtl/over ~ 64M
+ 8-12 байт на каждую строку = в теории до 100М строк можно побороть.

maytonТы брутфорсишь наш первый вариант который Naive Hash-table(NHT) ?- не, не знаю, начальную идею уже озвучивал - разбивка по длинам, дальше по 8-ми битам хеша - потом внутри этих групп по 24-битам отсеивание.
- теперь уже как бы есть для себя эталон - можно попробовать насколько не точным будет использовать второй хеш, а не полное сравнение, для перепроверки копия/коллизия.

Регайся в sourceforgeвроде была учётка, но я пока FPC/Delphi, если пройду по тестам засуржу в С ))

ничего вы там не распараллелите. Подумайте над алгоритмом.- когда ос читает диск/пишет данные в твой буфер, а ты в это время читаешь предыдущий буфер/наполняешь структуру - можно и сэкономить несколько секунд )
- да и финальная стадия очень просится в несколько потоков, только для каждого уже нужно будет +128М для 24 битного сита.
...
Рейтинг: 0 / 0
13.09.2017, 23:32
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520836
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Bred eFeMDima Tкачай список- ужо, это я из-за него и психанул - как оказалось там 7 раз одно и то же в кучу слито.
- ну и строки одинаковой длины - хороший тест.
В паспортах нет повторов.
Bred eFeMничего вы там не распараллелите. Подумайте над алгоритмом.- когда ос читает диск/пишет данные в твой буфер, а ты в это время читаешь предыдущий буфер/наполняешь структуру - можно и сэкономить несколько секунд )
- да и финальная стадия очень просится в несколько потоков, только для каждого уже нужно будет +128М для 24 битного сита.
Не совсем так: ОС занимается упреждающим чтением, т.е. пока ты парсишь очередной прочитанный кусок, в это время виндовс готовит тебе следующий.
...
Рейтинг: 0 / 0
14.09.2017, 07:02
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39520865
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Bred eFeMвроде была учётка, но я пока FPC/Delphi, если пройду по тестам засуржу в С ))
Ну Окей. Пускай на FPC. Главное чтоб работало быстро.. Ультра-быстро.

- когда ос читает диск/пишет данные в твой буфер, а ты в это время читаешь предыдущий буфер/наполняешь структуру - можно и сэкономить несколько секунд )
- да и финальная стадия очень просится в несколько потоков, только для каждого уже нужно будет +128М для 24 битного сита.
Да Async I/O мы попробуем. Но это техника применительна ко всем алгоритмам которые мы делаем.
По сути это просто технический trick. Мы его обязательно учтем. Но КМК самое главное - это понять
наши входные данные и выбрать подход.
...
Рейтинг: 0 / 0
14.09.2017, 08:42
| Ответить | Цитировать | Написать  
Тяпничная унификация
    #39521075
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДрузья. По поводу параллелизма. Не спешите. Данный алгоритм - последовательный
по своей природе. Если у вас дисковое хранилище на базе RAID-0 то пробуйте. Но
нам будет очень сложно обобщить ваши результаты на обычные конфигурации.

Во всех остальных случаях (рабочая станция + 1 физический диск) - не заморачивайтесь!
Не тратьте время на ерунду! У вас узким местом будет канал дисковой подсистемы
и ничего вы там не распараллелите.
Ты плохо думаешь о рабочих станциях: обычный бюджетный SSD на SATA3 выдает 400-500 Мб/сек. последовательного чтения. Наш случай.
Мой i7 в одно ядро парсит со скоростью 100-240 Мб/сек. Чем короче строки, тем ниже скорость.

Цифры говорят что есть чем занять простаивающие ядра.

Другой вопрос как сравнивать производительность многопоточного и однопоточного алгоритмов ?
ИМХО это разные весовые категории, поэтому однопоточные надо сравнивать с однопоточными.
...
Рейтинг: 0 / 0
14.09.2017, 13:18
| Ответить | Цитировать | Написать  
25 сообщений из 227, страница 8 из 10
  8  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная унификация
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]