1 биллион челлендж

Так и тесты бы были другими на подготовленные данные

Шутка

На хорошо подготовленных данных, формируем лишь header для DBF в начале файла и всё!
Затраченное время будет миллисекунды.

Скорее всего эта фирма занимается обработкой данных с всего мира.
Теоретически, если бы данные были подготовлены хорошо, то не возникла бы необходимость в разработке алгоритма для принятия их из CSV.

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

Кстати, все реализации топорные, ничего интересного. И везде встречается:

        catch (IOException e) {
            throw new RuntimeException(e);
        }

По заранее подготовленным данным в правильно лежащей таблице: Elapsed: 2.958 sec

Думаю тут стоит указать количество байт, занятых этой правильной таблицей (по сравнению с оригинальным текстовым файлом), и тип накопителя, на котором она лежит. Потому как исходный текстовый файл 13ГБ и только на чтение его даже с 500МБ/с ссд уйдёт как раз 25сек. Ну и дисковый кеш может заметно испортить результаты.

На всякий случай - я не претендую на Гуру КликХауза.

Сижу вот экспериментирую с разными вариантами «правильных таблиц».

Думаю тут стоит указать количество байт,

Если ENGINE = MergeTree и просто ORDER BY - то на всё про всё 66МБ. Но самая долгая вставка.

Если тот же MergeTree плюс еще и PARTITION BY по первым буквами city - то 59МБ, и вставка чуть быстрее.

Если ENGINE = Log, то самая быстрая вставка, но размер уже 5,6ГБ.

Пока мне кажется, что вставка в Log плюс MATERIALIZED VIEW на ней сразу с агрегацией в ENGINE = AggregatingMergeTree самое красивое получается. Оно ж на SELECT тогда совсем доли миллисекунд тратит.

Он в 66МБ запихал миллиард строчек? Из них можно сделать назад селектом исходные данные?

Ну да, весь миллиард запихал.

SELECT count(*)
FROM measurements

Query id: bce513fb-42a4-44c8-8bca-3cdb4b0e6f39

┌────count()─┐
│ 1000000000 │
└────────────┘

1 row in set. Elapsed: 0.002 sec. 

count то он показывает, а извлечь каждую строчку в отдельности он может? Дело в том, что в 66МБ всего 500 миллионов битов, получается по пол бита на строчку. Даже если выкинуть названия и хранить только температуры, это какое-то чудо.

SELECT
	table,
	formatReadableSize(sum(bytes)) as size
FROM
	system.parts
WHERE
	table = 'measurements'
GROUP BY table 
;

|table       |size     |
|------------|---------|
|measurements|66.70 MiB|

он же колоночный. Еще и жмёт.

У меня тут настоящая рабочая таблица на миллиард записей - 6ГБ. Если её перенести в PostgreSQL, в нормальную строчную РСУБД - она же будет 120ГБ. Тоже... в целом - чудо, можно сказать.

Данные хранятся сжатыми, по умолчанию, по моему LZ4.

Может там предагрегированные записи какие-то а не исходные данные? Колонка то по сути одна и правда - это температуры. Названий всего 400 или сколько там, много места они занять не должны. Может он заранее объединил одинаковые числа например? Порядок строк сохраняется?

Данные там рандом, он не должен хорошо сжиматься, если только строки не отсортировать предварительно.

При вставке строки сортируются красно-черным деревом.

$ grep Moscow measurements.txt | wc -l
2420614

SELECT count(*) FROM measurements WHERE city = 'Moscow';
2420614

Всё сходится. И жмёт, и сам решает где-как хранить, и о дублях думает. Умный зараза. Аж страшно, что умнее меня.

А, ну ясно, тогда это нечестно точно. Чтоб совсем наглядно стало - надо взять таблицы где все температуры будут нерандомные и равны средним, в итоге база кликхауса будет занимать примерно 5-10кбайт, а алгоритм из задачи будет отрабатывать за какое-то незаметное время.

Почему нечестно? Понимаю еще, претензию, чтобы время вставки учитывать в общем.

SELECT
	table,
	bytes as size
FROM
	system.parts
WHERE
	table = 'measurements'
;

|table       |size    |
|------------|--------|
|measurements|25421538|
|measurements|25419727|
|measurements|11346066|
|measurements|4000868 |
|measurements|1045690 |
|measurements|1042728 |
|measurements|1046127 |
|measurements|622259  |

Я вот понятия не имею почему он решил эту таблицу разбить именно на 8 частей. Ему виднее.

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

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

и твоих олимпиадников из яндекса

Ну, во первых они ко мне никакого отношения не имеют.

На джаве у меня отрабатывает быстрее сей

Я надеюсь, мы оба не верим в сказки и чудеса. Не могут одни и те же действия на компилируемом низкоуровневом языке и на языке, компилируемом в байткод и выполняемом на виртуальной машине с кучей проверок и сборкой мусора выполняться одинаково, не говоря уже о том, что во втором случае будет быстрее. Это физически невозможно, при одних и тех же действиях бизнес логики, java выполняет больше действий фактически.

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

Как хорошо, что в швятом питоне всегда можно:

import gc
gc.disable()

компилируемом в байткод и выполняемом на виртуальной машине

это просто интерпретатор как питон или php.

либо в реализациях на C

мне жалко места чтобы померять насколько бомжественный питон будет быстрее си (ну если джава «быстрее», то почему бы нет)

это просто интерпретатор как питон или php.

И это доказывает что?

мне жалко места чтобы померять насколько бомжественный питон

Еще раз: там либо проблемы в замерах, либо измеряется скорость разных действий.

Да понятно, что такого быть не может… НО все равно сравните кто-нить питон с этой обрыганской джавой. В 3.11 скорость вроде вкачали

Кроме того в java есть кэширование кода, мы время кэширования игнорируем или как, ну т.е. время первой jit компиляции (простите, если не совсем корректно формулирую).

Т.е. оцените идиотизм ситуации: создатели java давно поняли, что делают оверхэную херню и решили: а давайте как сделаем сохранение результатов jit компиляции в виде нативного кода, т.е. это что? Они изобрели использование нативных исполняемых файлов? Серьезно? А не судьба просто сделать еще один компилятор исходного кода в нативные бинари без этих плясок с байткодом и т.п….

Я всегда горячо поддерживаю стремление мужчин помериться пиписьками. Привет участникам соревнований! Всем удачи! Пусть победит сильнейший!

rust в этой задаче всех уиграет, да еще и безопасно.

либо измеряется скорость разных действий.

Это вполне имеет смысл. Если на языке А можно легко и изящно сделать то, что на языке Б получится совершить только с большими усилиями, то отчего мы должны ограничивать более развитый язык? Вообще, имеет смысл сравнивать только идеоматичный код (мы же потом как-то собираемся использовать результаты замеров в реальной жизни?) и если для С идеоматичным будет байтолюбство и утехи с указателями, а для Clojure — распараллеливание с помощью STM и immutable data structure’s, то как раз правильно будет измерить скорость разных действий и посмотреть какой подход в данном случае выгодней.

Closure vs Java? JVM vs JVM???

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

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

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

А что вас смущает?

уделать умный рантайм

Ты так говоришь, как будто этот «умный рантайм» писали не люди… к тому же этому «умному» хотя бы приблизиться к результатам «глупого»…

Это вполне имеет смысл

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

С другой стороны, мы ступаем на начало обсуждения: «быстро+сложно» против «медленно+легко+железо дешевое».

Ну ты же понимаешь что его писали люди которые с этим рантаймом работают годами и за это получают деньги. Причем там не один человек.
И вся эта сложность спрятана под капотом runtime. Вот кстати, если взять какой-нибудь computer language benchmark и посмотреть код реализаций которые уделали Java (на c,cpp,c#) то можно увидеть только две причины почему Java была разбита в пух и прах: 1) прямая работа SIMD операциями 2) Биндинг через FFI к какой-нибудь нативной либе (реализации на С# так делали, с тем же regex).

Ну ты же понимаешь что его писали люди которые с этим рантаймом работают годами и за это получают деньги

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

только две причины почему Java была разбита в пух и прах

Да большинство бенчей джава сливает и без simd (имею ввиду в сравнении с c/c++)

Биндинг через FFI к какой-нибудь нативной либе (реализации на С# так делали

Либа написана на c/c++ ? Т.е. мы доказали что c/c++ быстрее java, какая неожиданность.

Т.е. мы доказали что c/c++ быстрее java, какая неожиданнос

А в либе опять же SIMD скорее всего, хотя возможно в случае regex у Java он хуже реализован.

Да большинство бенчей джава сливает и без simd

Открой computer language benchmark и посмотри сам, загляни в код, покажи как в реализациях без прямой работы с SIMD регистрами java сливает (разумеется у CPP компиллеров тоже есть автовекторизация циклов).

измерить скорость разных действий и посмотреть какой подход в данном случае выгодней

Эталонная жабная реализация работает на моей машине ~212 секунд (3 минуты 32 секунды); простое чтение построчно всего файла на Clojure — уже 98 секунд (1 минута 38 секунд), примерно половина этого времени. Оба варианта работают в один поток.

(defn read-file [filename]
  (line-seq (io/reader filename)))

(time (dorun (read-file "dev/resources/measurements.txt")))
;; "Elapsed time: 98344.165526 msecs" 

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

Чтение файла в несколько потоков (в несколько кусков) теоретически может помочь с производительностью, но краткость и понятность, конечно, пострадают.

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

Если ENGINE = MergeTree и просто ORDER BY - то на всё про всё 66МБ.

Верится, конечно, с трудом. Но. Если повнимательнее посмотреть на данные, то мы увидим, что станций там всего 413 штук, значение температуры представлено максимум тремя цифрами плюс знак числа, то есть это не более 1000 * 2 значений. Если помножить одно на другое, то получится 413 * 2000 = 826000. Это в теории. На практике же, учитывая нормальное распределение температур, уникальных строк в файле будет ещё меньше.

Давайте посмотрим:

>>> len(set(open('measurements.txt')))
364636
>>> 364636 / 1e9 * 100
0.0364636

То есть уникальных строк во всём файле менее, чем 0.04% от общего количества.

Таких записей миллиард.

А чем задача с миллиардом записей принципиально отличается от задачи с 1k, или 100500Q записей? Решение-то всё равно O(n)…

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

Там ещё забавнее с ENGINE = Memory - и размер 26ГБ (sic!) и ещё и медленная до невозможности получается.

А вообще ничего лучше Log + MatView так и не нашел. Загружаем около 60 секунд в Log. И потом выбираем за 0.003 из MatView при любых условиях.

Знаете фокус, как из 13ГБ файла получить таблицу в памяти на 26ГБ ?

Решение-то всё равно O(n)…

С одним потоком ты тут каши не сваришь.

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

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

Кстати, все реализации топорные, ничего интересного. И везде встречается:

Чем предлагаешь заменить?

Зависит от скорости процессора, и скорости источника данных. Если данные вынимаются, к примеру, из сети, со скоростью 64kbit/s., то однопоточной обработки на большинстве процессоров будет хватать с избытком…

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

Предлагаю заменить другим языком программирования без checked exceptions.

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

Питонисты вычислительную математику и численные методы игнорируют полностью?

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

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

оно и в ClickHouse так умеет.

CREATE TABLE default.measurements_f
(
    `city` String,
    `temperature` Float32
)
ENGINE = File('CSV', 'measurements.txt')
SETTINGS format_csv_delimiter = ';';

Только все прелести БД так не работают. Это ровно то же, что и SELECT FROM json по сути получается.

И одноразовая выборка min, avg, max - стабильные ~25 секунд. Это точно хуже лучшего варианта на Java.

У этой задачи палка о двух концах: если у нас данные часто апдейтятся, то разумнее класть в бд и оттуда работать. Если надо посчитать разово, то по-моему не имеет значения, займет это 30 секунд или 300.

Тест идиотский, как обычно не имеет ничего общего с реальными задачами.

Давай сам. Мне лень искать очевидное.

А если этот анон прав (я исходные данные не смотрел), то уж действительно выглядит полным идиотизмом обрабатывать этот файл каждый раз с нуля вместе с дублями.

Поправьте, если не так понял суть.