Pull to refresh

Comments 50

Так и знал, что стоит не читать все сразу :-D Провалил 5 тест.

Поздравления потенциальным победителям!
Надо было в анонсе размер призов указать до ката… Жаль проморгал конкурс.
Ого, мне раньше казалось, что такая точность определения координат для точности таймера в 100нс это фантастика
Ужс, коллеги, из 49 только 12 решений выдали разумные результаты, без серьезных багов. Неужто это мы так после 9 мая паршиво напрограммили? :))
Моя, например, упала в 5ом тесте по памяти, пытаясь загрузить 2.5ГБ файла в 30ГБ оперативки :)
По другим не скажу, изучение еще в процессе.
Странно, перепрогнал тесты — использование памяти во время тестирования поднимается на жалкие 100мБ, свободной памяти остается ~30Гб — но все равно падает с ошибкой памяти. Другие программы жрали гораздо больше, и не падали.
Падает при выделении new byte[2147483647] (2^31 — 1). Да и System.in.available() выдает лишь int, а не long, так что все-равно чтение одним куском бы не работало.
Был вариант, читающий кусками, но он работал на несколько миллисекунд медленее. Был напрасно выброшен)

Да и в любом случае, я и не надеялся оказаться даже в первой половине, с моими-то знаниями java :)
так available может дать и один байт, ему никто не запрещает выдавать результат сегментами произвольных размеров…
У моей либо фатальная ошибка в алгоритме, либо что-то с крашами — 2 теста пройдены, причем с неплохим результатом. Остальное — ужс. Завтра гляну, что там.
Интересно было бы вообще сравнить готовые алгоритмы за вычетом багов. Просто для спортивного интереса, без переписывания всего кода.
Итого, как я и думал, мой алгоритм поиска оказался одним из лучших по скорости и устойчивости, хоть и не идеальным. 2Гб тест он прошел посредственно, но все-равно достойно (хотя может тут время добавила математика — поиск всех пересечений 255 окружностей). А вот математику я завалил — чтобы уменьшить количество действий предположил, что результат обязательно будет лежать на диске шириной в 1км для каждой окружности и так фильтровал точки пересечений. Идея, может, и не плоха, но на трех больших тестах привела к отбрасыванию вообще всех точек :) Багфикс тут не поможет, нужна переделка.
У меня, к примеру, итоговый расчет местоположения (как раз пересечения окружностей и последующая кластеризация) занимает порядка 0.8 — 5мс на моем проце. Не самая, имхо, тяжелая часть задачи.
Ну так, видно, кто чему уделял внимание и с чем чаще работал :))
Весь мой опыт java — этот конкурс и одна прожка под android :) Я, в основном, backend/server-side'щик на других ЯП.
Участвовал так, ради интереса.
Ну так я тоже серверщик, часто работал с огромными массивами данных, потому идея загрузить все в память была мне против шерсти, от того и работал напрямую с входящим потоком, а поиск делал по ключевым точкам — 18 нулей либо 19 единиц. Поиск по двум последовательностям необходим на случай, если одна из них будет рассечена, либо слишком удалена от начала файла.
Если есть желание, вот мой полный код: paste2.org/M67IjdFE
В мой метод findPoints() вместо строк 170-188 можно в чистом виде добавить вызов вашего searchCenter() и посмотреть на производительность такого гибрида.
Я еще поизучаю все исходники, когда соберусь по времени :)
Грузить разом нехорошо, если данных очень много. 2.5ГБ на машине с 30ГБ оперативки совсем не много, а один единственный вызов new+read выходил у меня ощутимо быстрее, чем серия последовательных чтений. Но стоило уделить больше внимания краевым случаям :)
Итого, как и говорил, я скрестил ежа и паукаваше и мое решение, чтобы проверить скорость своего алгоритма поиска:
Скорость сравнивал с результатами habrunit, lany, моим и вашим изначальным решением. Как водится, у меня возникла еще одна идея по ускорению алгоритма поиска, которая почти не повлияла на результат, но довольно показательна.
Идея
По большому счету для нахождения оффсета достаточно для наших данных выполнить такой цикл:
while(j < read && c0 < 18)
{
   int bit = 49 - buffer[j];
   c0=c0*bit+bit;
   j += 10;
}

После выхода из цикла если c0 >= 18, то результат равен offset=-read+j-c0*10-427401


Результаты в виде таблички. Замерялось только время в миллисекундах по 5-10 раз и выбиралось лучшее (не среднее!):
http://runserver.net/temp/table.htm
Скриншот таблички, если лень открывать ссылку


Выводы:
— скорость алгоритма тов habrunit ошеломляет. Конкурентов ему в принципе нет
— на моей станции (мобильный i5-2500S) математика считается относительно медленно, потому ваш алгоритм кластеризации обрабатывается относительно медленно на больших тестах, особенно на 2М тесте
— мой старый поиск, а особенно ужатый в shader-style, как описано выше, работает так же или быстрее, чем алгоритм поиска паттерна у lany, кроме 2М теста, но это не имеет никакого значения из-за моего провала с математикой. В который раз посыпаю голову пеплом и выдергиваю остатки седых волос. :(
Я насчитал 15, удовлетворяющих всем требованиям.

Эта задача оказалась очень коварна: легко написать решение, которое быстро и правильно работает на маленьких тестах, поленится сгенерировать несколько вариантов больших тестов, на которых вылазят проблемы — и так и отправить.
UFO just landed and posted this here
Спасибо BarsMonster за конкурс. В прошлый раз я оказался 9м и был следующим в очереди на инвайт.

К сожалению моя Java оказалась не достаточно сильна — замена моего Reader-a на Reader AKashta вроде выводила бы меня на 2е место с шансами на 1е.

Тесты немного огорчили, по количеству и отсутствию тестов с 2я спутниками.
Интересно, что на более слабом i5-3427U (8G памяти, SSD) результаты получаются на несколко балов выше.
HT нет. Уменя получилось оптимальное число потоков — n/2+2 для процессора с HT и n/2 для процессора без HT.
Моё решение использует 4 потока:
1) Чтение файлов + расчёт x,y,r для каждого спутника.
2) Подсчёт начальной точки (после 2х или 3х спутников) и печать результата когда все спутники обработаны
3) Итеративный поиск оптимальной точки на основе уже считанных спутников.
4) Оценка результата и остановка если время кончается или ожидается ухудшение результата.
Ничего вы суровые парни. Мне и в голову бы не пришло распараллеливать то, что работает полсекунды. Может, зря, конечно. Моё решение в один поток.
Таки поймал двух зайцев :-)
Полный мой код лежит здесь. Glonass.java — незапакованный вариант. Он выдаёт немного другой результат, так как при ужимании где-то пришлось подкрутить логику, но отличие буквально на сантиметры.

По-моему, залогом успеха оказались тесты. Когда я понял, что с MD5 всё просто (первые 18 бит нигде не повторяются дальше, можно искать только их), я реализовал простой алгоритм двумерной оптимизации, где целевая функция была суммой квадратов расстояний от пробной точки до ближайшей точки каждого из допустимых колец (то есть любая точка, попадающая во все кольца, имела значение целевой функции 0). Я шёл от начала координат в четыре стороны с фиксированным шагом в поисках точки с наименьшим значением целевой функции. Если такая не находилась, шаг уменьшался вдвое и так пока он не станет слишком маленьким или мы не попадём в ноль. Два авторских теста сразу заработали, что обрадовало. Тогда я сгенерировал 15'000 случайных тестов (по 1'000 для различного количества спутников от 2 до 255 с пропусками). Тесты сразу дали общую картину и показали, куда стремиться:
Тесты
N=2; tests = 1000; err = 101; miss = 65; avgErr = 26.419818975075056
N=3; tests = 1000; err = 27; miss = 0; avgErr = 17.18386006640053
N=4; tests = 1000; err = 3; miss = 0; avgErr = 12.471251745777266
N=5; tests = 1000; err = 1; miss = 0; avgErr = 10.26658013001998
N=6; tests = 1000; err = 0; miss = 0; avgErr = 8.384866411024463
N=8; tests = 1000; err = 1; miss = 0; avgErr = 6.761668562530785
N=10; tests = 1000; err = 0; miss = 0; avgErr = 5.39886100515112
N=15; tests = 1000; err = 0; miss = 0; avgErr = 3.708876777322233
N=20; tests = 1000; err = 0; miss = 0; avgErr = 2.7836350095460176
N=30; tests = 1000; err = 0; miss = 0; avgErr = 1.9093947714394366
N=50; tests = 1000; err = 0; miss = 0; avgErr = 1.106928626235093
N=100; tests = 1000; err = 0; miss = 0; avgErr = 0.5885234831376301
N=150; tests = 1000; err = 1; miss = 0; avgErr = 0.41466940914913764
N=200; tests = 1000; err = 0; miss = 0; avgErr = 0.2923054804172029
N=255; tests = 1000; err = 0; miss = 0; avgErr = 0.2240679725000143
Total: tests = 15000; err = 134; miss = 65; avgErr = 6.284088749458255

err — это если мы вообще не нашли точку с целевой функцией 0 (например, свалились в локальный минимум), miss — если ошиблись больше, чем на 1000 метров. Miss для двух спутников — это нормально, там возможно два решения. Err и miss не учитываются в подсчёте avgErr. Ошибки были, хоть и работало супербыстро (раз в 20 быстрее итогового варианта, наверно).

Без тестов разработка превратилась бы в гадание на кофейной гуще. Смешно было читать комментарии про «6 или 9 спутников будут давать очень хороший результат, IMHO». Я-то видел, что 255 спутников повышают точность в среднем раз в 20.

Для улучшения средней точности надо находить не любую точку в области, а близкую к середине. Для этого я модицифировал целевую функцию. Внутри области она падала ниже нуля и равнялась минус произведению расстояний от пробной точки до ближайшей границы кольца. Так внутри получилась плавная функция, которая на границе допустимой области уходит в 0 и непрерывно стыкуется с внешней целевой функцией. Это увеличило точность процентов на 30, но не решило проблем с локальными минимумами. Я добавил движение по разным углам, если четыре изначальных направления не дали улучшения, но всё равно проблемные тесты остались.

Тогда я стал по-умному выбирать стартовую точку из всевозможных пересечений внешних и внутренних окружностей всех колец. Это сразу замедлило работу на порядок, но решило проблемы с оптимизацией. Вот один из последних отчётов по тестам:
Тесты
N=2; tests = 1000; err = 0; miss = 63; avgErr = 28.575585249312216
N=3; tests = 1000; err = 0; miss = 0; avgErr = 13.251180627746319
N=4; tests = 1000; err = 0; miss = 0; avgErr = 9.527123529965028
N=5; tests = 1000; err = 0; miss = 0; avgErr = 7.825816219103384
N=6; tests = 1000; err = 0; miss = 0; avgErr = 6.582336714290559
N=8; tests = 1000; err = 0; miss = 0; avgErr = 5.231786878805114
N=10; tests = 1000; err = 0; miss = 0; avgErr = 4.46787460510955
N=15; tests = 1000; err = 0; miss = 0; avgErr = 2.984066934628246
N=20; tests = 1000; err = 0; miss = 0; avgErr = 2.357838284898613
N=30; tests = 1000; err = 0; miss = 0; avgErr = 1.5727939974888727
N=50; tests = 1000; err = 0; miss = 0; avgErr = 0.9525235480146365
N=100; tests = 1000; err = 0; miss = 0; avgErr = 0.5020066798945585
N=150; tests = 1000; err = 0; miss = 0; avgErr = 0.3270679902543295
N=200; tests = 1000; err = 0; miss = 0; avgErr = 0.24243998933614222
N=255; tests = 1000; err = 0; miss = 0; avgErr = 0.1896709694010934
Total: tests = 15000; err = 0; miss = 63; avgErr = 5.542602286104438


После этого я стал тестировать граничные случаи. А что если каждый второй спутник очень близко к предыдущему? А что если приёмник в точности между парами спутников? А что если первые 250 спутников рядом, а только последние 5 разбросаны? Я подозревал, что тесты будут «заряжены», поэтому хотел точное и надёжное решение в ущерб производительности.

Производительность до конца не давала покоя. У меня комп заметно медленнее, чем у BarsMonster'а, поэтому я не мог нормально оценить свои шансы. Я не знал, сколько будет тестов для малого числа спутников, сколько для большого, насколько тесты будут плохими. Малое число спутников обрабатывалось быстро, но потом скорость падала почти по кубу. Я до конца порывался вставить лимит в перебор спутников для генерации стартовой точки, но всё же решил этого не делать, хотя шансов запороть тест было очень мало (даже если хорошая стартовая точка не будет найдена, оптимизация работала больше, чем в 99% случаев и от начала координат). Кому интересно, можете заменить в моём решении i<c&&H>0 на i<Math.min(c,10) и погонять. Конечно, зная тесты заранее, я бы поставил лимит в 50, но в 10 честнее.

Спасибо BarsMonster за интересную задачку. Также выражаю благодарность жене (KVie), которая с пониманием отнеслась к тому, что я кучу времени на выходных просидел за компом, и сама предложила свой ноутбук для проверки тестов на другой платформе :-)
А не проще было веса для точек считать и потмо усреднять с весами?
Не знаю. Вы можете подправить моё решение и испытать :-) По факту в итоговой версии выбор стартовой точки тормозит существенно больше, чем последующая оптимизация.
Красивое решение поиска!

Удивило что многие рискнули проигнорировать «Переводы строк — не документированы, лучше на это не закладываться. » и (удачно) предположили \r\n как в опубликованных тестах.

А ещё проигнорирован результат функции skip(), хотя в документации сказано, что может быть пропущено меньше заказанного.
Я тупо .trim() подписал, сделав решение устойчивым не только к разным переводам строк, но и к лишним пробелам, например.

Если бы .skip() у BarsMonster'а не сработал, я бы сейчас рвал на себе волосы :-)
Во время чтения можно сделать следующие оптимизации:
* Вместо того, чтобы считывать 660к данных, для первух спутников можно посчитать более точный минимум и максимум расстояния (Если спутник в 20000км от центра, то он как минимум 20000-6378 км от приёмника)
* Начиная со 2го/3го спутника, когда местоположение приёмника примерно известно, можно считать маленький кусок — меньше килобайта.
* Pattern.find работает быстрее indexOf, так как использует Boyer–Moore
Самое крутое чтение у habrunit'а — посмотрите его реализацию. Он читает где-то 320 байт всего для каждого спутника. К сожалению, такую реализацию не сделаешь компактной. Пропустить вначале можно было, но там не так много. Минимальное расстояние 10'000, то есть скипать можно только 3'622 километров, примерно 120'000 отсчётов можно скипнуть. Оптимизировать чтение последующих спутников, основываясь на предыдущих, я бы не стал без крайней необходимости: можно напороться на какой-нибудь corner-case. Надо тестировать все суровые конфигурации.

Я не использовал ни Pattern.find, ни indexOf. Вообще переводить это в джавовские строки считаю бредом. У меня массив байт, и я тупо искал там нужные значения сравнением. Не верю, что в этом месте я существенно проиграл по сравнению с продвинутыми алгоритмами поиска подстроки: вряд ли тут даже единицы миллисекунд можно выиграть. Искомая подстрока-то всего 18 символов. Создавать для этой задачи лишние объекты в куче никакого смысла нет.

Ну и плюс я всё же старался сделать решение компактным. Любая нетривиальность в этом месте снижает шансы на победу. Вообще самое сложное в задаче было уравновесить скорость, точность и компактность в идеальном соотношении. К примеру, я легко могу сделать решение существенно компактнее, потеряв в точности (но при этом все тесты всё ещё будут проходить).
Изменив в вашем Glonass.java
for (int offset = 0;; offset += 10)
на
for (int offset = 120000;; offset += 10)
Я получил на 0.2 балла больше (в сумме на 6и тестах)
Не знаю стоит ли это 5и символов :)

У habrunit действительно круто — предпосчёт 256 маркеров. Судя по коду он читает до 16и килобайт. При оптимальном распределении маркеров:
665000 возможных расстояний делить на 256 это примерно 2600 байт.

Я искал пересечения краёв колец и мог оценить разброс точек. Считывание маленького участка используется только при маленьком разбросе.
Вроде ваше решение было одним их тех, которые падали у меня при массовом прогоне с нестандартными переносами строк.
Так вроде или точно? И с каким сообщением падали? :-)
Могу вечером прогнать еще разок, если интересно. Как-то смысла особого нет.
Прочитав последовательность до первой единицы — мы однозначно определяем остаток деления на 10 от сдвига последовательности.
Я делал наоборот: сперва шёл с шагом 10, а, найдя нужную подстроку, отступал от неё назад с шагом 1. От начала последовательности был риск напороться на длинную серию единиц и потерять время (конечно, немного, но всё же), а перед нужной подстрокой всегда гарантированно была смена единицы на ноль (я заранее проверил, что первый бит спутникового сигнала — 1, последний — 0).
Большое спасибо BarsMonster за конкурс. Задача оказалась интересной и многогранной, разработка решения превратилась в квест, в котором нахождение каждого артефакта приводило к улучшению результата. Я тоже сделал генератор тестов и автоматический подсчет баллов, но тесты гонял вручную, автоматизировать все до конца времени не было. Поздравляю lany с заслуженной победой.
Всмотрелся в ваше решение. Так вы больше 50 спутников в принципе не анализируете! Вот вам повезло-то! Будь шестой тест 50+10, а не 40+10, вы бы попали :-) Ну что ж, я вас тоже поздравляю с отличным результатом :-)
Кстати, любопытный момент. Рассмотрим программу:
public class Glonass {
  public static void main(String...args) {
    System.out.println("0 0");
  }
}
Она наберёт почти 60 баллов и войдёт в верхнюю половину результатов :-)
Только с точки зрения формулы очков — требованиям-то по точности она не удовлетворяет, вся таблица будет красная )
Я просто из этого:
Если время работы более 5 секунд на процессоре i7-3820 с HT или ошибка определения координат превышает 1000 метров — то результат не засчитывается.
решил, что красные тесты не должны вообще давать вклад в итог. А по факту дают. Ну мне лично разницы нет, конечно, но уже на пятое место это повлияет.
Табличка результатов обновлена — теперь явно отделены решения, проходящие все тесты.
Прикольно — у победитиля время расчёта практически не изменяет от сложности задчи (остаётся близким к минимуму). Круто.
С чего это? 0.2 секунды против 0.8 секунд — существенная разница :-)
В отличие от решений других лидеров — моё может давать существенно разные результаты в разные запуски.

BarsMonster, на моей машине моё решение обгоняет habrunit примерно на 0.2 балла при прогоне каждого теста 20 раз подряд (для усреднения результатов и разогрева cache).

Можете сделать у себя такую пороверку для лидеров?

for i in range(6):
    for r in range(20):
      name = 'tests/' + str(i+1)
      check(name)
У меня все тесты запускались 3 раза и время усреднялось, время выполнения у всех немного плавает.
можно теперь еще и аналогичный конкурс на аппаратную реализацию провести.
В RSS спойлер не работает, замучался скроллить вниз.
У нас был инженер, который писал код в таком же стиле как победитель. Возможно это он и есть.
Sign up to leave a comment.