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

Слишком. Много. Памяти.

Так не интересно, можно весь файл в ОЗУ прочитать.

А в чём челлендж? Обычная задача

Написать самый быстрый.

Надо просто писать его на С, а не на джаве.

уууу вариант с кликхаусом уже кто-то сделал - 45 секунд.

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

Просто SQLite использовать (справится «на раз»).
Вообщем бы проблемы не было, если бы даже DBF использовали.
Кстати ODBC очень шустро работает.

Вот реализации на других ЯП https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell

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

URL на данные?

Нужно самому сгенерить, в репе https://github.com/gunnarmorling/1brc есть скрипт

Жду реализацию на лиспе от lovesan

Вот: https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CreateMeasurements.java

челлендж … Пишем на джаве

АХАХАХАХА рассмешнил так рассмешнил

Не?

with open('govno.dat') as fp:
  _, val = next(fp).split(';')
  min = max = avg = float(val)
  for line in fp:
    _, val = line.split(';')
    val = float(val)
    min = val if val < min else min
    max = val if val > max else max
    avg = (avg + val) / 2
print(f"{min=}, {max=}, {avg=}")

Среднее неправильно. НО ВСЕ РАВНО питон лучше

https://en.wikipedia.org/wiki/List_of_cities_by_average_temperature

Math.round(m * 10.0) / 10.0;

Я бы начал с того, что написал бы свою функцию для перевода строки числа во float. В данном случае подошёл бы даже LUT.

double measurement() {
    double m = ThreadLocalRandom.current().nextGaussian(meanTemperature, 10);
    return Math.round(m * 10.0) / 10.0;
}

...

    bw.write(";" + station.measurement());

Я правильно понимаю, что в жабке можно складывать даублы со строками?

чем лучше

Сделать что-то тяжелое на заведомо тормозящем языке, который не подходит для написания тяжелый задач. Это там людям настолько нечем заняться?

Ifran - марокканский Воронеж, а в Кейптауне как в Сочи

тем что десять строк для любой задачи.

да, у String перегружен оператор +, он приклеивает к строке toString() операнда. Ну и для примитивов тоже работает.

и результат не важен, главное что 10 строк?

Победит Perl.
Алгоритмы для работы с строками у него очень хорошие.

Шутка

Получите данные и распишитесь http://bulk.openweathermap.org/sample/

Спасибо за ответ) Оно, возможно, так и удобно, но как-то не конкретно, не правильно. Какой-то JavaScript уже получается. Это, мне кажется, как раз результат того, что в языке есть дженерики и перегузка операторов. В C++, кстати, та же петрушка с <<. Какой-то, извините, урод придумал, а потом в школе этому детей учат.

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

>>> ";" + 3.14
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate str (not "float") to str

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

Ну и на порядок следования смотреть надо, 2+2+«ы» = 4ы, «ы»+2+2 = ы22. Приведение типа происходит при первом сложении со строкой.

«ы»+2+2 = ы22

А «ы»+2*2 даст «ы4»?

Шутка

1С-ники обычно именно с этого начинают: «2» + 2 = «22»

да, оно ж на приоритетах операций базируется. Если не нравится порядок, ставь скобки (а лучше форматируй нормально).

1С-ники обычно именно с этого начинают: «2» + 2 = «22»

В 1С в цепочке сложений достаточно глянуть тип крайнего левого. А в Java вполне может быть до середины сложного выражения числа, а потом, внезапно, строка. Жуть.

Если не нравится порядок, ставь скобки (а лучше форматируй нормально).

При конкатенации нормально. Не нравится порядок у iostream<<. Лучше бы <<= и >>= переопределили. А так при выводе половина операций должна быть в скобках, а половина — не обязательно.

Бинарный поиск

уууу вариант с кликхаусом уже кто-то сделал - 45 секунд.

судя по

 SELECT [bla-bla-bla]
    FROM (SELECT c1 as city, c2 as temperature FROM file('measurements.txt', CSV))

Надо бы попробовать правильно порезать в PARTITION BY, PRIMARY KEY, ORDER BY. 45 секунд для КХ на миллиарде записей - это очень много.

Это же вместе со вставкой из csv-ки, которая генерится по условию испытания.

Ну, на мой взгляд - если не просто «читаем JSON/CSV всё подряд», а «читаем в правильно подготовленную для этого таблицу» - поиск должен быть существенно быстрее.

Вечером попробую потыкать.

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

• Параграф правил
• Ссылка на файл данных
• Ссылка куда слать исходники для таблицы лидеров

И Всё.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

#define MAX_STATIONS 1000
#define MAX_NAMESIZE 32
#define HSIZE 5381

typedef struct {
  unsigned int hash;
  unsigned int next;
  int       min;
  int       max;
  long long sum;
  long long count;
  char      name[MAX_NAMESIZE];
} station;

static station sts[MAX_STATIONS];
static unsigned int hst[HSIZE];
static unsigned int nst;



static char b[1048576];
static size_t bs, bp;
static unsigned long lines;

static int stcmp(void const *a, void const *b) { return strcmp(((station*)a)->name, ((station*)b)->name); }

int main(void) {
  ssize_t r;
  size_t p;
  unsigned int hash;
  char c;
  station *st;
  unsigned int sti;
  int neg;
  unsigned int val, vv, h;
  
  while(1) {
    r = read(0, b+bs, sizeof(b)-bs);
    if(r<0) { fprintf(stderr, "warning: read error %d (%s)\n", errno, strerror(errno)); break; }
    if(!r) break;
    bs += r;
    for(h=5381,p=bp; p<bs; p++) {
      if((c=b[p])==';') {
        for(sti=hst[h%HSIZE]; ; sti=st->next) {
          if(!sti) {
            if(nst==MAX_STATIONS) { fprintf(stderr, "too many stations"); return -1; }
            st = sts+(sti=nst++);
            st->hash = h;
            bcopy(b+bp, st->name, p-bp);
            st->name[p-bp] = 0;
            st->next = hst[h%HSIZE];
            hst[h%HSIZE] = sti+1;
            break;
          }
          if((st=sts+(sti-1))->hash==h && !strncmp(st->name,b+bp,p-bp) && !st->name[p-bp]) break;
        }
        p++;
        if(bs-p<2) break;
        if(b[p]!='-') neg=1; else { neg=-1; p++; }
        val = 0;
        while(1) {
          if(p>=bs || (c=b[p])<'0' || c>'9') break;
          vv = val*10+(c-'0');
          if(vv/10!=val) { fprintf(stderr, "bad input data\n"); return -1; }
          val = vv; p++;
        }
        if(p>=bs) break;
        if(b[p]=='.') {
          p++;
          if(bs-p<2 || (c=b[p])<'0' || c>'9') break;
          vv = val*10+(c-'0');
          if(vv/10!=val) { fprintf(stderr, "bad input data\n"); return -1; }
          val = vv; p++;
        } else {
          vv = val*10;
          if(vv/10!=val) { fprintf(stderr, "bad input data\n"); return -1; }
          val = vv;
        }
        if(p>=bs) break;
        if(b[p]!='\n' || (int)val<0) { fprintf(stderr, "bad input data\n"); return -1; }
        neg*=val;
        if(!st->count || neg<st->min) st->min = neg;
        if(!st->count || neg>st->max) st->max = neg;
        st->sum += neg;
        st->count++;
        bp = p+1; h=5381;
        lines++;
        continue;
      }
      h += h<<5;
      h ^= (unsigned char)(b[p]);
    }
    if(!bp) { fprintf(stderr, "bad input data\n"); return -1; }
    if(bs -= bp) bcopy(b+bp, b, bs);
    bp = 0;
  }
  if(lines!=1000000000) fprintf(stderr, "warning: got %lu lines, not 1000000000\n", lines);
  qsort(sts, nst, sizeof(*sts), stcmp);
  for(val=0,st=sts; val<nst; val++,st++) {
    neg = st->sum/st->count;
    printf("%s%s=%d.%u/%d.%u/%d.%u", val?", ":"{", st->name, st->min/10, abs(st->min)%10, neg/10, abs(neg)%10, st->max/10, abs(st->max)%10);
  }
  printf(nst?"}\n":"{}\n");
  return 0;
}

вроде компилируется и на файле из 7 строк работает, дальше не проверял

чё будет с именами станций в юникоде?

$gcc -O2 firkax.c -o firkax
$time ./firkax < measurements.txt

real	0m24,800s
user	0m23,593s
sys	0m1,193s

их эталонный вариант:

$./calculate_average.sh

real	3m2,147s
user	2m59,572s
sys	0m2,998s

последние записи:

Ürümqi=-41.4/7.4/56.2, İzmir=-29.1/17.9/73.8

Сортировка может пострадать походу. Ну мне это уже лень делать, юникодные сортировки тащить. Хотя поскольку в «условии» есть захардкоженный список станций то можно и сортировку захардкодить (предварительно заполнить ими список в нужном порядке). Но это уже читерство и всё равно лень.

А с вариантами на C и C++ если сравнить?

Не знаю. С КликХаузом тут воюю. Отложил сюда, чтоб потом сравнить с КХ.

vvn_black

что-то вот так с наскока - действительно не фонтан.

Прямо, в лоб, с чтением данных из файла: Elapsed: 27.970 sec, что очень похоже на Си-вариант господина firkax

По заранее подготовленным данным в правильно лежащей таблице: Elapsed: 2.958 sec, чего понятно ни у кого близко нет. Только вот сам INSERT из CSV в такую таблицу - страшно долгий.

Ладно, сдаюсь.

SQLite попробуйте.
Он действительно хорош.
А эта задача для него - «самое то».

Хорошие цифры. Как ОП прочитал, первая мысль была - зачем кодить, когда есть кликхаус, прошёл по ссылке, а там уже и результат есть.

Нужно спросить у chatgpt...

На ноутбучной рязане с 8 ядрами получил следующие результаты:

• [firkax] gcc -O2: 23-25 секунды (си, как я понял в один поток)

• [spullara] native-image: 13-14 секунд (graalvm 21)

• [spullara] java: 7-10 секунд (openjdk 21)

Каждый тест запускал несколько раз, поэтому время плавает.

данным в правильно лежащей таблице: Elapsed: 2.958 sec, чего понятно ни у кого близко нет.

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

Прямо, в лоб, с чтением данных из файла: Elapsed: 27.970 sec

Ну, чо rumgot? На джаве у меня отрабатывает быстрее сей и твоих олимпиадников из яндекса или кто там этот кликхаус написал?