Поиск ближайшего значения

неплохо бы СУБД указывать.

Проблема в том, что в колонке unixtime нет значений делящихся без остатка на time. как за относительно короткое время на 64 битной системе (SSE, AVX, 4 ядра) найти в первой колонке значения делящиеся с минимальным остатком?

Если честно, условия задачи не понятны. Можно переформулировать? Вообще если нужно тупо сократить кол-во операций, можно использовать определенные признаки делимости, но как я уже сказал выше из этого

time = 1357052400 time = time + 86400 либо time = 15:00:00

вообще делитель не очевиден.

csv

Надо среди огромной кучи юникстаймов найти времена наиближайшие к 15:00

вообще делитель не очевиден.

Да, сдвиг нужен.

Пробежаться по всему массиву, найти минимум. Параллелится без проблем.

O(N)

двачая тому, кто сможет за меньшее время

махонькая база:

https://api.bitcoincharts.com/v1/csv/btceUSD.csv.gz

Хм. Погоди, а что значит первое условие?

time = 1357052400 time = time + 86400 либо time = 15:00:00

Т.е.

1. Есть N-ное кол-во дат в unixtime. И есть конкретная дата (1357052400), ориентируясь на которую нужно найти время ближе к 15:00, и при этом с минимальными затратами
2. Или же есть N-ное кол-во дат в unixtime, но без всяких условий, среди всех этих дат нужно найти те, время которых ближе к 15:00

Вот это не понятно. И еще вдогонку, сразу же поясните, отсортированы ли уже имеющиемся стампы?

К каждому дню надо найти ближайшее к 15:00 время.

А зачем тебе делить на time, если можно вычесть? Все равно там частное всегда 1, а остаток на 2 порядка меньше всегда.

А если можно вычесть, то нафик вычитать, когда можно тупо отсортировать.

Стало быть O(log(N))

Десятки миллионов строк - это копейки, считанные секунды даже если обычным awk добавить слева колонку с остатком, потом отсортировать sort'ом, какие там нафиг ядра и SSE.

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

Да это я сумбурно объяснил, надо было сразу про время написать.

Сортировка всего массива O(log(N))

Поиск в сортированном массиве значения ближайшего к заданному это еще O(log(N))

Фух. Если честно у меня голова сейчас не варит. Я думаю метод в лоб, как предложили выше, будет самым простым и не геморным. Но если реально нужна производительность, и таких данных будут гигабайты, и нужно будет постоянно с этим работать, можно попробывать посочинять что-нибудь на ходу.
[пьяный_сочинитель_mode]
Ну, к примеру, раз это тупо кол-во секунд, можно делить на группы в 30 лямов (примерно столько на 1 год выходит, я все сейчас буду округленно говорить ибо считать лень), и потом эти данные индексировать. Т.е. грубо говоря алгоритм такой. Даты в 70-том году, находятся в диапазоне от 0 до 30 миллионов, даты в 71 от 30 до 60 и т.д. и т.п. Потом эти группы сохраняются в индекс, и при проходе таблицы, учитываются только те, которые которые находятся в своем диапазоне. Сравнение 2 чисел будет всяко проще чем распарс стампа каждый раз, когда нужно выдернуть время, чтобы узнать что там.
Так, покрайней мере твой алгоритм будет анализировать только те стампы, которые входят в свой диапазон. Ну и по аналогии этот диапазон можно просчитывать и для месяцев, и даже для дней, но это я думаю уже точно будет лишнее. Но только повторюсь, вся эта белиберда может быть уместна, если у тебя реально тучи эти стампов, и они постоянно добавляются в интенсивном режиме и т.д. и т.п. Если это нужно сделать 1 раз, то нафиг никакой индекс/диапазоны/весь этот бред не нужны. Берешь машину побольше и как сверху уже сказали - анализируешь все записи по порядку.
[/пьяный_сочинитель_mode]

Проблема решена:

which.min(abs(as.numeric(mydata$UNIXTIME)-(1357052400+step)))

За пару минут таблица жуется.

это у вас видимо некий журнал, где время всегда увеличивается?

если записей в день много и идут с примерно одинаковой частотой, то решение в один проход используя две операции:

- «найти следующий диапазон» - от текущей позиции тупо пропустить например 1000 строк/записей чтобы попасть не позже 14.00 след.дня

- «ближайшая метка к 15.00» - линейно перебирать от найденной на пред.шаге до следующей после 15.00

городить огород с сортировками/деревьями/хешами явно не стоит - вычислительная часть мизер, всё упрётся в скорость чтения файла.

Сортировка всего массива O(log(N))

ээээ... нет

Если таблица в файле csv и все числа в десятичной системе, то чтение чисел займет времени много больше, чем их обработка.

2 минуты обработка всех дней это долго?

ступил

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

Так придется пройти таблицу 1500 раз. Сколько циклов получится?

Нет. Один.

Каким образом, если тебе нужен остаток для каждого дня?

Нет.

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