Спецы ассемблера
Спецы ассемблера, есть такой вопрос, надо сравнить два столбика:
Что будет быстрей, питон и база данных в SQLite или построчное сравнение в чистом ассемблере? В принципе SQLite написан тоже на Си,
и думаю там какие-нибудь алгоритмы выборки задействованы, как работать с большими объёмами данных или всё-таки ассемблер быстрей?
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
Быстрей будет не бегать от языка к языку, а идти в каком-нибудь одном выбранном направлении. Выбрал скриптизёрство, там и продолжай в том же духе. Оно в принципе на любом языке считается. Проблемы производительности обычно не в расчётах, а в UI и вводе-выводе - там потребление ресурсов и задержки на порядок-два больше.
Чистый ассемблер - дерьмо. Писать надо сразу в нулях и единицах, тогда быстрее всего будет. Профи ставят 8 пальцев на цифровые клавиши и за одно движение вводят сразу целый байт (8 бит). Немного потренироваться и будешь как пианист программировать.
)))
И это вся информация?Где они находятся, какой размер, как часто нужно сравнивать, какие типы данных нужно сравнивать и т.п.?
Вначале нужно определить где узкое место, а после уже думать как с ним бороться.
где они находятся: текстовой файл TSV.
какой размер: пока что 80 миллионов строк.
как часто нужно сравнивать: время от времени.
какие типы данных нужно сравнивать: текст, присвоил каждому хомяку хеш, коллизии маловероятны.
где узкое место, а после уже думать как с ним бороться: пока что интересуюсь где выборка быстрей?
***
Население Земли 8 миллиардов, выборка по Германии 80 миллионов, далее ещё выборка...
и из этого списка нужно найти 8 хомяков, если это делать в питоне то выглядит это так:
c.execute("SELECT homjak FROM homjak WHERE homjak IN (SELECT homjak FROM homjak_de)")
Вопрос заключается в том, какие алгоритмы сортировки и поиска задействованы в SQL базах?
Допустим если писать на ассемблере, то я начну тупо перебирать строку за строкой, сравнивать,
а если дописать алгоритм, то уже можно будет прыгать к начальной букве (тоесть сократить диапазон)
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
Проблемы производительности... Профи ставят 8 пальцев на цифровые клавиши и за одно движение вводят сразу целый байт (8 бит).
Вот ещё один пример, плохой производительности, вроде исходные данные равны - оба программисты, оба сишарпники, оба мигранты!
но один ездит на машине за 2 тыщи (типа бинарный), а второй на машине за 80 тыщ, типа как нормальный пацан, но диски дешманские..
Как им помочь? Первому приобрести нормальную машину = нестыдный фургончик, а второму диски? Ответ прост - установить Метамаск!
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
Вопрос заключается в том, какие алгоритмы сортировки и поиска задействованы в SQL базах?
Я думаю, не на вашем уровне совершенствовать алгоритмы поиска в СУБД.
Допустим если писать на ассемблере, то я начну тупо перебирать строку за строкой, сравнивать,
а если дописать алгоритм, то уже можно будет прыгать к начальной букве (тоесть сократить диапазон)
Существующие алгоритмы сортировок и поиска по тексту примерно так и работают - по символам. Все очевидные вещи давно сделаны за вас и вылизаны до предела. Просто пользуйтесь тем, что есть, и всё. Если не удовлетворяет выборка из 80М строк в БД, значит что-то не то делаете. У меня есть таблица с сотнями миллионов строк, и по простым полям, типа чисел (тот же айди), выборка идёт долю секунды. А вот по полнотекстовым полям - да, там сложнее. И чем длиннее искомая строка, тем медленнее. Т.е. строка в 1-3 символа ищется ощутимо быстрее, чем в 4 и более. Но полнотекстовый поиск всегда был такой на больших объёмах данных. Тут либо большие текстовые поля разбивать на более мелкие, либо вводить дополнительный простой критерий сортировки для отсева.
Ну и ещё зависит, сколько данных запрашиваете и передаёте на клиента. Если запросить 10к лишь айдишников, то произойдёт быстро. А если по 40 полей к каждому, да ещё с кучей больших текстовых данных - будет долго передаваться и отображаться. Тут скорее долго отображаться будет. Я даже если тысячи полей запрашиваю, так что на каждую строку по, скажем, 10кБ приходится, это всё равно передаётся быстро. А вот рисуется в UI долго, если без виртуализации. Так что затык может быть в отрисовке, а не в запросе. Вы это проверяли?
Оба варианта какие-то крайности ненужные.
Один взял кредит на крутую тачку, чтобы понтоваться, но съэкономил на мелочах. Это выглядит смешно, т.к. реально обеспеченный не будет на дисках экономить 5% цены машины.
А другой другой взял слишком дешёвую тачку с кучей проблем, в которую ещё столько же вложить надо денег, плюс время, плюс всё равно она сыпаться будет.
Если у челов есть деньги (программистами же работают, а не поломойками), то тут оптимально где-то посередине - машина 3-5 лет за 20-30 тыщь. Такая внешне достаточно "нестыдная" будет, и вложений сильно требовать не будет.
Метамаск тут самое плохое решение. Лучше уж в рулетку всё спустить или на баб.
Я думаю, не на вашем уровне совершенствовать алгоритмы поиска в СУБД.
Так я как раз об этом и говорю, что не разбираюсь и мне хотелось понять хотя бы принципы работы!
Итак, повторяюсь ещё раз, первый вариант, работать с питоном и sqlite, типа лучше быстрей не будет.
Второй вариант, попросить "специально обученных людей" написать мне программку на ассемблере,
мне не надо никаких вычислений, просто сравнивать два столбика и записывать дубликат в третий!
по моим представлениям я имел бы в папке 4 файла, и работало бы это всё на любом компьютере:
азм.ехе
хомяк80млн.тхт
хомяк1тыща.тхт
дубликат.тхт
мне надо исключительно лишь построчное сравнение, возникает вопрос - нужны ли мне базы данных?
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
просто сравнивать два столбика и записывать дубликат в третий!
то бишь нужно не просто построчное сравнение строк из двух файлов, а поиск строки из одного файла в другом?
Если один файл достаточно маленький и его можно разместить в ОЗУ, то никакие базы не нужны.
Также не нужна и прога на ассемблере. То, что хорошо написанная прога на ассемблере будет быстрее любого решения - это как бы само собой разумеется, но вот имеется ли в этом смысл?
текстовой файл TSV.
видимо CSV? - не оптимально, каждую строку нужно будет еще парсить. Или там всего лишь один столбец?
как часто нужно сравнивать: время от времени.
?? раз в час, раз в день, раз в неделю и т.п.
Начинать нужно с правильной постановки задачи. Даже само само слово "сравнивать" может интерпретироваться по разному. Какой именно алгоритм сравнения? Похоже, что нужно не сравнение, а поиск.
если это делать в питоне то выглядит это так
-----
А где там питон?
Да и SQL тебе еще долго учить придется...
какие алгоритмы сортировки и поиска задействованы в SQL базах?
-----
Разные. Часто - сменяемые в соответствии с набранной статистикой.
а если дописать
-----
Ну так допиши и будем обсуждать что хорошо и где потери...
прыгать к начальной букве
-----
Угу... осталось понять как это делать... кстати - а почему не к последней? или не ко второй с конца? И почему - к букве? Может к цифирьке получше будет? Особенно на х64...
А вообще-то чтобы понимать об чем речь стоит обратится к "Д.Кнутт, Искуство программирования, т.3 Сортировка и Поиск"...
видимо CSV? - не оптимально, каждую строку нужно будет еще парсить. Или там всего лишь один столбец?
Это такой же текстовый формат для представления таблиц баз данных как и CSV - https://ru.wikipedia.org/wiki/TSV
1 Столбец. А то что по поиску, брать 1 строку и прогонять по списку, потом следующую - я и спрашиваю это "быстрей"?
но разве в SQLite, нет определённых алгоритмов сравнения и поиска? например скачет сразу к начальной букве итп?
например мы ищем "Сидорова", я предполагаю что база данных перепрыгнет Ивановых и Петровых, начнёт сразу с буквы С
Или это не так? У меня список не отсортирован, но какая-то же польза должна быть, в чем преимущество хранения в базе?
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
хорошо написанная прога на ассемблере будет быстрее любого решения - это как бы само собой разумеется, но вот имеется ли в этом смысл?
Смысл, в быстроте и не использовать лишних программ, 1 ехешник - менял бы только текстовые файлы.
Это сравнить как "ушисвой_82" якобы гоняет выделенный сервер для сильверлайт за 9 евро в месяц,
чтобы разместить 1 страницу в хтмл (резюме?), сделать конечно это можно но зачем? Деньги на ветер.
Так и здесь, если выборка из миллионов строк окажется быстрей, но зачем мне сервер и базы данных.
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
ПС.
Один из способов ускорения поиска по тексту:
- все приводится к одному регистру
- к каждому слову строится хеш по правилу - гласные удаляем, согласные - заменяем 5 битами, строим длинное целое по 5 битным секциям,
- сортируем полученные хеши, при наличии дубликатов думаем как с ними работать
- пользуем бинарный поиск по хешам.
А где там питон? Да и SQL тебе еще долго учить придется...
я экспериментирую с SQLite, в среде питон юпитер ноутбук, если бы обращался через С++, прилепил ту же самую стоку поиска и сказал С++, хватит умничать! 
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
база данных перепрыгнет
-----
А почему "она должна" это делать?
У меня список не отсортирован
-----
И чо?
Нет гарантии упорядоченности - будешь полным сканированием обходится... хоть в файле, хоть в базе.
Либо почитаешь указанное выше и подумаешь что и как делать...
в чем преимущество хранения в базе?
-----
Напиши то что тебе надо на чистом питоне и вопрос отпадет.
Население Земли 8 миллиардов, выборка по Германии 80 миллионов, далее ещё выборка...и из этого списка нужно найти 8 хомяков, если это делать в питоне то выглядит это так:
Так а что там в данных лежит, есть какой-то пример?
Если данные не обновляются (часто), и запросы стандартные, то быстрее загрузить все в память и искать вручную. Но конечно надо индексы сгенерировать один раз ну и еще чего-нибудь соптимизировать по ходу дела. БД нужна если записи будут добавляться/изменяться, поскольку надо правильно индексы обновлять), нужна многопользовательность, транзакциональность, fault tolerance, scalability и пр. навороты. sqlight достаточно легкая и быстрая база и ее вполне можно использовать. Чтобы не гадать надо просто попробовать и решить - это же пару строк.
Вопрос заключается в том, какие алгоритмы сортировки и поиска задействованы в SQL базах?
Это отдельная специальность и там куча книг и статей. Туда не надо лезть, если не хочешь в Оракл устроиться.
Допустим если писать на ассемблере, то я начну тупо перебирать строку за строкой, сравнивать,
Не надо ничего на ассемблере писать. Можешь попробовать Rust и потом расскажешь, как у него со скоростью.
Это такой же текстовый формат для представления таблиц баз данных как и CSV
Вообще то лично для меня файл в формате CSV - это файл который сожрёт excel. Какой разделитель, можно указать.
А то что по поиску, брать 1 строку и прогонять по списку, потом следующую - я и спрашиваю это "быстрей"?
то что вы спрашиваете относится к алгоритмам. Есть достаточно много вариантов, в зависимости от правильной постановки задачи.
Если один из списков достаточно маленький, то лучше всего держать его в памяти.
в чем преимущество хранения в базе?
А чем удобнее хранить данные в excel, а не в word? Поиск и сортировка всего лишь небольшая часть преимуществ, но совсем не главная
присвоил каждому хомяку хеш
Тут думать даже не надо: строки добивать до 64 байт, сравнивать xmm-регистрами =) Две операции загрузки, одна сравнивания.
ооо, даже не верится, я когда то потратил денег на оптимизации баз, но ни на одном форуме никто не сказал да о возможности относительно быстрой сортировки базы в миллиард записей )) и пришлось тупо сесть и придумать решение самому, что я и успешно сделал. Но никому не скажу как ))
Кстати есть оказывается тулза которая поддерживает таки миллиард строчек, но я еще не тестировал ее
Power BI от Microsoft – что это?
ооо, даже не верится, я когда то потратил денег на оптимизации баз, но ни на одном форуме никто не сказал да о возможности относительно быстрой сортировки базы в миллиард записей )) и пришлось тупо сесть и придумать решение самому, что я и успешно сделал. Но никому не скажу как ))
Это только я не понял задачу, которую хотел решить 
Muenchausen? :) Зачем сортировать лярд записей? В БД для быстрой сортировки придумали индексы...
Кстати есть оказывается тулза которая поддерживает таки миллиард строчек, но я еще не тестировал ее
Любая БД поддерживает лярд строчек. Даже есть все строчки пронумеровать обычным 32 разрядным интом, будет больше 4 лярдов строк...
Тоесть имеем текстовый файл например 90 гиг, где база из двух столбцов, в первом 30 значный код , во втором дата , и таких строчек по моему 870 млн штук, сколько времени нужно чтобы просто отсортировать по тридцатизначному коду в порядке возрастания ?
Тоесть имеем текстовый файл например 90 гиг, где база из двух столбцов, в первом 30 значный код , во втором дата , и таких строчек по моему 870 млн штук, сколько времени нужно чтобы просто отсортировать по тридцатизначному коду в порядке возрастания ?
Еще раз, все зависит от того, что тебе нужно иметь на выходе.
Самое простое и быстрое решение:
1) создать БД
2) сделать табличку из 2- колонок (id и дата)
3) добавить индекс по колонке код
4) дальше просто считываешь все эти 870млн строк и добавляешь в БД.
Отсортированные данные готовы. Осталось их только выбрать: select * from <table> order by <id>. Ну очевидно, что 870млн строк за раз никому не надо, поэтому имеет смысл сделать вывод по частям: select * from <table> order by <id> offset X rows fetch next Y rows only (для MSSQL).
Сколько на это уйдет времени сказать не могу, но это будет не то, чтобы очень долго.
Другой способ - создать индекс самостоятельно. Т.е. рядом с текстовым файлом появится еще один файл, в котором будет сохранен двухсвяхный список.
Если нужен совсем хардкор, то различные алгоритмы сортировки гуглятся на раз. Если в исходном файле данные одинковой длины, то жизнь несколько упрощается.
2й и 3й способы будут гарантированно медленнее и геморройнее в реализации. Зато 100% свое :D
Выбирай любое подходящее тебе решение :)
А почему играет роль одинаковая длина ? По идее я могу в текстовом исходном файле сделать автозамену 1 на 01 , 2 на 02 .. и тогда все однозначные станут двузначными и длига кода станет везде одинаковой. Я читал что при сортировке оно берет например первую строку и сравнивает со всеми следующими снизу, тоесть 870 млн сравниваний. Итого имеем прогрессию как бы ( 1+870млн)/2 × 870 млн что грубо равно 900 млн х 400 млн = 36000000 млн млн или 36 млн млн млн операций , это же куча времени !
А почему играет роль одинаковая длина ?
Потому что
1) в строках одинаковой длины легче навигация
2) строки одинаковой длины проще менять местами
Пример:
AAAA
DDDD
CCCC
BBBB
против
AA
DDD
BBBB
C
Очевидно, что в 1-ом случае для того, чтобы узнать начало какой-либо строки надо знать просто номер этой строки. Во втором случае для того, чтобы узнать начало 3-й строки нужно прочитать первые две (ну или построить индексный файл и хранить там начало и длину каждой строки).
С сортировкой все еще забавнее. Если для перестановки 2-й и 4-й строк понадобится всего 2 операции записи, то во стором случае понадобится 3 операции записи, при этом 3-я операция - это все, что между 2-й и 4-й строчкой.
Т.е. если у тебя 1млн строк и ты хочешь поменять местами 2-ю и предпоследнюю строки, то ты перезапишешь практически весь файл. А чтение и запись - это очень медленные операции.
Я читал что при сортировке оно берет например первую строку и сравнивает со всеми следующими снизу, тоесть 870 млн сравниваний. Итого имеем прогрессию как бы ( 1+870млн)/2 × 870 млн что грубо равно 900 млн х 400 млн = 36000000 млн млн или 36 млн млн млн операций , это же куча времени !
Это не самый быстрый алгоритм :)
Есть более эффективные сортировки: https://www.toptal.com/developers/sorting-algorithms
Тоесть имеем текстовый файл например 90 гиг, где база из двух столбцов, в первом 30 значный код , во втором дата , и таких строчек по моему 870 млн штук, сколько времени нужно чтобы просто отсортировать по тридцатизначному коду в порядке возрастания ?
Зачем текстовый файл на 90 гиг? Зачем 30-значный код для миллиарда (10 знаков) записей? Зачем сортировать без смысла, без запроса? Разве что предварительная сортировка, но она делается один раз.
ну как бы анализ событий случившихся за многие годы, а результат кодирован тридцатизнаком, причем там тысячи за день, просто скидывалось в текстовик годами, но формат соблюден. Задача найти топ 10 например повторяющихся, но мне хватит даже если все их просто отсортировать по возрастанию а там я уже макросом пройдусь по текстовику. А текстовик потому что я ексцелем иногда балуюсь, с текста легче вынимать и там нет ограничения на 90 гб файлразмер.
Отсортированные данные готовы.
-----
Ээээ... каким образом?
гуглятся на раз
-----
Ээээ... а зачем? для файлового варианта все есть в системе...
но это будет не то, чтобы очень долго
------
Исходная задача говорит что - в сопоставлении с другими решениями - долго - нужно будет читать последовательно два списка, при этом один перечитывать сначала.
А почему играет роль одинаковая длина ?
-----
Ты хоть немножко программируешь?
Напиши простую программку - прочитать эн-ную строку из файла.
Один вариант - для равнодлинных строк, другой - для переменной длинны.
И погоняй на своих 870 млн строк.
Все поймешь...
#15 - смотри условия применимости.
Если вернуться к изначальному вопросу ТС, то питон и SQLite будет быстрее :) При этом как в кодинге, так и в работе. Зачем сортировать исходный файл все еще не понял :D
Индекс одноколоночной таблички - 100% дублирование оной.
Нет, индекс одноколоночной таблички избавляет от изменения порядка строк в исходнике. И больших объемах это важно.
Ээээ... каким образом?
Отсортированные данные выбираются простым SQL запросом.
Исходная задача говорит что - в сопоставлении с другими решениями - долго - нужно будет читать последовательно два списка, при этом один перечитывать сначала.
Про исходную задачу мы знаем ничего.
Решением в лоб - сортируем один список (загнав его в БД), дальше идем по элетентам 2-ого списка и ищем эти элементы в отсортированном. Все. Дальше уже надо смотреть на конкретный юз-кейс.
как в кодинге, так и в работе
-----
В кодинге - немного больше. См. sort /?
В работе - квадратично меньше.
избавляет от изменения порядка строк в исходнике
-----
За счет построения полного и упорядоченного дубля. У дубля как раз будет изменение порядка строк которого ты пытаешься избежать.
Все тоже самое получается физическим упорядочением исходного, но без избыточности на поддержание двух копий.
Отсортированные данные выбираются простым SQL запросом.
-----
Ну так Я и спрашиваю - каким образом при вставках неупорядоченных данных получается упорядоченный набор
Про исходную задачу мы знаем
-----
сортируем один список (загнав его в БД)
-----
Это никогда не имело место быть - добавление записей в базу никоим образом не упорядочивает записи...
Ну так Я и спрашиваю - каким образом при вставках неупорядоченных данных получается упорядоченный набор
Говорил уже - путем добавления к таблице индекса.
#8
Овет прост - да, решение с БД будет проще и выстрее, чем решение на ассемблере или любое другое самописное решение.
Это никогда не имело место быть - добавление записей в базу никоим образом не упорядочивает записи...
Само по себе добавление записи не упорядочивает, а если есть индекс, то 1) упорядоченный вывод становится в разы быстрее и 2) поиск по таблице (что и надо ТС) сокращается с 80млн до 8 сравнений.
путем добавления к таблице индекса
------
1. индекс не меняет положение записей в таблице
2. индекс одноколоночной таблицы содержит полную копию данных таблицы
3. индекс сортируется в указанном порядке
Т.е. ты 100% дублируешь количество данных и выполняешь сортировку всего объема данных.
Ну плюс еще оверхед по навигации через индекс - чтение индекса, затем чтение данных из таблицы.
Ну и количество чтений будет не единичным - не всегда данные будут на кешированной странице.
Если озаботишься прочтением и осознанием упомянутого ранее метода, то можешь осознать,
что вопрос решается за один проход - одно последовательное чтение, без возвратов, без крос-навигации...
проще и выстрее
-----
Проще - с точки зрения кодинга - да. примерно на 8-мь строк меньше.. 
Насчет - быстрее - ой...
сокращается с 80млн до
8 сравнений
-----
8 сравнений на одно вхождение vs однократное линейное чтение всего массива...
и - да, можно поиграться с дополнительным акселерированием, но оно не даст большого выигрыша при строках переменной длинны...
Почитай про сортировку слиянием - модификация как раз даст нужный результат.
Это был самый полезный совет в этой теме, я чёта слишком сфокусировался на сравнении списков, а надо было слить всё в кучу и выцедить дубликаты,
решил через пару дней после прочтения и понятия сортировка слиянием, это же ежедневная работа любого администратора который работает с базами...
Вопросы и Ответы - Программируем калькулятор пособий для беженцев вместе.
назад
список