Майское хабрасоревнование: делаем свой ГЛОНАСС

    Шла холодная зима 2063 года… Вы, сидя в избушке в сибирских степях, попивая горячий чай, из ностальгических побуждений достали свой любимый раритетный смартфон образца 2014 года с поддержкой ГЛОНАСС — однако он почему-то не нашел ни одного спутника. Вдруг тишину разрезал пронзительный звонок красного правительственного телефона — голос на той стороне затараторил: оказалось все спутники ГЛОНАСС вышли из строя из-за неизвестного сбоя… (ТЗЧ? Закладки? Кто теперь разберет....)

    Что-ж, надежда теперь только на вас — нужно в кратчайшие сроки (к понедельнику) разработать новую систему спутниковой навигации с учетом достижений науки и техники 2063 года: в связи с тем, что термоядерные реакторы и аннигиляционные двигатели стали достаточно компактными, чтобы помещаться на борту спутника — их теперь фиксируют в одной точке в околоземном пространстве, никакой орбиты больше нет. Соответственно, альманах и эфемериды (параметры орбиты спутников) больше не нужно передавать со спутника на землю.

    Принцип функционирования ГЛОНАСС в 2063 году

    Дело происходит на двумерной плоскости. Заранее известно, что приемник гарантированно находится не далее 6378км от начала координат. Спутники — фиксированны в точках, отдаленных от центра координат на расстояние от 10тыс до 20тыс км. Каждый спутник передает одну и ту же псевдослучайную последовательность со скоростью передачи 1 Мегабит (миллион бит в секунду), сигнал мы принимаем с частотой 10 миллионов выборок в секунду. Т.к. каждый спутник передает сигнал на своей отдельной частоте — мы можем принимать их независимо.

    Псевдослучайная последовательность повторяется каждую секунду. Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают, однако из-за того, что расстояние от спутников до приемника разное — из-за скорости света мы получаем сигнал с задержкой (скорость света = 299792458 метров в секунду) — т.е. сначала принимаем «хвост» предыдущей последовательности, потом «голову» текущей. Вычислив задержку по сдвигу кодовой последовательности — мы можем оценить расстояние до спутника. Зная расстояние до нескольких спутников — мы можем примерно определить координаты.

    Схематично это будет выглядеть так: Радиус нарисованной окружности — вычисленная задержка сигнала умноженная на скорость света.


    Спутники и приемник стоят на месте — нет никакого доплеровского сдвига, и не нужно учитывать релятивистские эффекты (в том числе гравитационные). Т.е. по времени тут никаких хитростей.

    Формат входных данных

    Данные вводятся через стандартный ввод.
    Первая строка — число N от 2 до 255: количество спутников
    Далее описание N спутников: в отдельных строках — координаты X и Y спутника в метрах, относительно начала координат.
    Далее — 10млн цифр 0 или 1, принятая на земле псевдослучайная последовательность с этого спутника.

    Алгоритм генерации псевдослучайной последовательности (она всегда одна и та же):
    data = md5("3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446"+to_string(pos))
    

    Где pos — изменяется от 0 до 999999. Если первый символ data>'7' — то передается единица, иначе ноль.

    Приемник принимает сигнал с выборкой в 10 раз чаще, потому 0 и 1 повторяются в течении 10 последовательных выборок. Более частая выборка на приемнике позволяет точнее определить задержку распространения сигнала.

    Пример вывода: (принятая кодовая последовательность показана частично)
    2
    -6.83616e+006
    1.6126e+007
    000000000000000011111111110000000000000000000000000000000000[...]
    -1.07643e+007
    -1.48409e+007
    10000000000111111111100000000001111111111111111111111111111111111[...]
    


    Формат выходных данных

    Результаты — печатаются в стандартный вывод.
    Вещественные координаты приемника, разделенные пробелом — X и Y, в метрах, относительно начала координат.

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

    Пример выводимых данных:
    -1.81683e+006 -1.74334e+006

    Примеры файлов ввода/вывода — можно скачать тут: s.14.by/glonass-contest.zip

    Оценка результатов

    Если delta — ошибка определения координат в метрах и T — время затраченное на вычисление, то количество баллов вычисляется по формуле 100/(delta+10) + 10/(T+1). Если время работы более 5 секунд на процессоре i7-3820 с HT или ошибка определения координат превышает 100 1000 метров — то результат не засчитывается. Баллы по всем тестам суммируются.

    Язык программирования

    Разрешен только Java SE 7, сторонние библиотеки использовать не получится. Решение должно быть в одном файле, размером не более 20кБ. Вы не можете работать с сетью, обращаться к любым файлам на локальной машине, работать с нативным кодом (JNI и ко).

    Оформление решения, сроки и куда слать

    Решения принимаются до 23:59 (время Московское) 11 мая по адресу contest@14.by, файл с решением должен быть прикреплен к письму — не нужно вставлять код в само письмо!

    В первой строке решения должен быть комментарий вида:
    //@BarsMonster
    
    Где BarsMonster — имя вашего пользователя на HabraHabr (участвовать могут и read-only пользователи, регистрируйтесь)

    Призы

    Первое место по баллам — 2 BTC,
    второе — 1 BTC,
    третье — 0.5 BTC.

    Дополнительная номинация:
    За самое компактное решение, проходящее все тесты (по времени и требуемой точности) 1 BTC.

    Результаты будут опубликованы на хабре в понедельник-вторник, победители с read-only аккаунтами будут приглашены на хабр, ну и конечно мы попробуем пригласить победителей на собеседование.

    Послесловие

    Сдув пыль с полки шкафа вы достали древнюю папку, подписанную «ГЛОНАСС: референс-имплементация», вероятно содержащую реализацию приемника на одном из древних языков программирования… Возможно через какое-то время вам удасться разобраться, что там написано…

    Следите за обновлениями статьи и всем удачи!

    Update 10.05.2014 2:03: Подкорректировано описание кодовой последовательности. Выполнятся будет на 64-битной Java (-Xms10g -Xmx30g). Переводы строк — не документированы, лучше на это не закладываться.
    Update 10.05.2014 10:23: Данные гарантированно будут в дисковом кеше, чтобы тестировать решение, а не диск (скорость его мне и так известна, 500Мб/сек).
    Update 10.05.2014 13:18: Округление координат спутников создает слишком много неясностей. Гарантируется точность координат спутников до 1мм (3 знака после запятой в метрах). Качайте новый файл — в него добавлен 3-й тест с высокой точностью. Все тесты для финального тестирования перегенерированы с высокой точностью.
    Update 11.05.2014 18:00: Наконец пришли результаты распознавания текста программы. Оказалось, она написана на каком-то древнем языке программирования со странным названием — Эрэнэр. Похоже авторам очень нравились древние деньги. Судя по заметкам на полях — скорость и точность работы оставляла желать лучшего.
    Скрытый текст
    //Might have some OCR errors
    <?
    
    $startTime = microtime(true);
    set_time_limit(99999999);
    ini_set('memory_limit', '-1');
    
    fscan("%d", $n);
    
    $sat = array();
    
    for($i=0;$i<$n;$i++)
    {
    	fscan("%f", $sx);	
    	fscan("%f", $sy);	
    	fscan("%s", $sequence);	
    
    	$sat[] = array("sx"=>$sx, "sy"=>$sy, "sq" => $sequence);
    }
    
    $ref = "";
    //Calculate reference sequence
    for($i=0;$i<10000000;$i++)
    {
    	$hash = md5("3.1415926535897932384626433832795O28841971693993751O582O9749445923O78164O62862O8998628O34825342117O67982148O865132823O6647O938446".((int)((($i)%1OOOOOOO/1O))));
    	$ref .= ($hash[0]>'7')?"1":"0";
    }
    
    $ref .= $ref;
    
    //Calculate pseudorange
    for($i=0;$i<$n;$i++)
    {
    	$sat[$i]["range"] = (10000000.0-intval(strpos($ref, $sat[$i]["sq"])))/10000000.0*299792458.0;//Meters
    }
    
    $best = 10E100;
    for($x=-7000000;$x<7000000;$x+=2000)
    {
    	for($y=-7000000;$y<7000000;$y+=2000)
    	{
    		$delta = 0;
    		for($i=0;$i<$n;$i++)
    			$delta += abs($sat[$i]["range"]-sqrt(pow($x-$sat[$i]["sx"],2)+pow($y-$sat[$i]["sy"],2)));
    		if($delta<$best)
    		{
    			$best = $delta;
    			$bestx = $x;
    			$besty = $y;
    		}
    	}
    }
    
    print("$bestx $besty\n);
    echo "\n\nExecution time: ".(microtime(true)-$startTime);
    ?>
    

    Update 11.05.2014 20:11: Время неумолимо подходит к концу — поток решений становится все более бурным. Результаты будут опубликованы не позднее вторника. За временем приема последних решений проследит безжалостный робот.
    Update 14.05.2014 23:22: Опубликованы результаты.
    WayRay
    72,00
    Мы разрабатываем голографические дисплеи
    Поделиться публикацией

    Комментарии 176

      +2
      У вас что-то не так с размерностями: «с частотой 1 мбит».
      А ещё «Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают»; поясните, пожалуйста, как синхронизировались часы? (отсутствие одновременности для разных систем отсчёта)
        +1
        Насчет размерности вы правы, теперь там «скорость передачи».

        Точное локальное время в 2063 году — это рутина :-) Поскольку у нас и спутники и приемник стоят на месте, релятивистские эффекты (в том числе и гравитационные) учитывать не нужно — со временем никаких хитростей нет.
        +9
        Это эксперименты с БАК привели к тому, что мир плоским стал, или термояд?
          +13
          Терри Пратчетт.
          +1
          Ещё вопрос. Случайная последовательность всегда приходит в сохранности, с точностью до бита?
          +5
          На мой взгляд, было бы технологичнее развернуть систему наподобие ejudge, чтобы можно было онлайн проверять свои решения. А задачка интересная, жаль, что не смогу поучаствовать :)
            +1
            Интересная задача, не ожидал, правда. Думал, полегче будет :)
              0
              to_string( (pos)%10000000/10 ) для pos = 13 вернет 1 или 0000001?
              +1
              Можно присылать отдельно «быстрое решение» и «компактное»?
                0
                Форматом оформления решения такая возможность не предусмотрена — так что нужно смотреть, где по вашему мнению у вас выше шансы..
                +3
                А я что-то не понял, откуда берется сдвиг? Тот пул нолей и единиц — это то, что отправляет каждый спутник, или уже сдвинутая посылка?
                  +3
                  Спутники — фиксированны в точках, отдаленных от центра координат на расстояние от 10 до 20тыс км

                  Подскажите, минимальное расстояние до спутника 10км или 10тыс км?
                    0
                    10тыс, отметил в тексте.
                    +1
                    А у вас приёмник в какой момент точно говорит значение бита кодовой последовательности? Скажем, приёмник находится на расстоянии в 200 метров от спутника, первым битом в принятой последовательности будет первый бит, или хвост?
                      0
                      Когда радиосигнал доходит до приемника — тогда бит приемник и увидит. Потому даже на 200 метрах — сначала «хвост».
                    • НЛО прилетело и опубликовало эту надпись здесь
                        +1
                        Чтобы волосы никто на себе не рвал — учитываться будет последняя присланная версия, но лучше этим не злоупотреблять и слать когда совершенно уверены :-)
                          +1
                          --не успел--
                          0
                          Координаты спутников точны или округляются до какого-то знака? Иными словами, можно ли в примере
                          -1.07643e+007
                          -1.48409e+007
                          считать, что точные координаты спутника -107643000, -148409000?

                          И как именно считается время в случае, если программа использует больше одного ядра?
                            +1
                            Округляются.
                            Время — естественно считается «wall clock», иначе не было бы смысла использовать несколько ядер.
                              +2
                              А до какого знака округляются? И вверх, вниз или к ближайшему целому?
                                0
                                Округление как обычно — «к ближайшему» десятичному знаку.
                                Это не значит, что округление именно до целого числа, может быть десятки метров, может быть 0.1м.
                                  0
                                  Будут ли все координаты в одном входном наборе округлены до одинакового числа значащих цифр?
                                    0
                                    Как минимум, если в конце будут нули — в научной записи одного из значений может оказаться меньше цифр, так что я бы не стал сильно закладываться на такие детали.
                                      +2
                                      Если мы знаем точное положение спутников, задача заключается в пересечении нескольких колец шириной 30 метров. А вот если, как в примере выше, положение спутников известно с точностью +-500 метров по каждой из осей, мы получаем ширину кольца больше 1км. И достичь высокой точности на таком тесте — задача уже совсем другая. Вы уверены, что это всего лишь деталь, на которую не надо закладываться?
                                        +1
                                        Смотрите обновление к статье, координаты будут точными.
                          +3
                          Можете выложить оффсеты для тестовых примеров?
                            +1
                            Можете объяснить следующую фразу:
                            сигнал мы принимаем с частотой 10 миллионов выборок в секунду

                            То есть мы можем принимать сигнал от 10 млн. спутников в секунду одновременно?
                              +1
                              От одного спутника. Если он отправляет 1.1.0.1, то мы получим 1111111111.1111111111.0000000000.1111111111
                                +7
                                Мне кажется, авторы перемудрили с заданием…
                                … а вот с точностью и однозначностью формулировок — явная недоработка.
                                Что такое «выборка» для меня до сих пор загадка, а додумывать как AterCattus — плохой вариант.
                                Честно, ждал задания, но, даже при 20-м прочтении я все еще не уверен что все понял правильно.
                                К тому же, на олимпиадах принято давать несколько примеров входных данных и ответы на них.
                                В общем, ждем новых и проработанных заданий по типу настоящих ТЗ в будущем.

                                Зы. Если вдруг, этим комментарием, я выиграю в номинации «самое коротное решение» — Вы знаете где меня искать;)
                                  0
                                  Полностью с Вами согласен, условие задания не совсем поняты, пример input/output есть:
                                  Примеры файлов ввода/вывода — можно скачать тут: s.14.by/glonass-contest.zip
                                    +2
                                    Почему додумывать-то.
                                    Источник сигнала за секунду выдает 1кк значений, приемник — 10кк. Значит каждый исходный бит повторяется на приемнике 10 раз подряд.
                                      +8
                                      Потому как многолетний опыт разработки подсказывает, что абсолютно любые выводы о требованиях к решению, сделанные путем логических выводов из ТЗ, ошибочны, где ошибкой является, как минимум, то что они не описаны в ТЗ, а требуют дополнительной работы от каждого исполнителя, вместо однократной от составителя ТЗ.
                                      Разумеется, Москва не сразу стро.. ТЗ не сразу становится хорошим, но это не повод выкладывать его настолько сырой вариант.
                                      Любая олимпиадная задача детерминирована на 147%, того же я ожидал и здесь.
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                          0
                                          Далее — 10млн цифр 0 или 1, принятая на земле псевдослучайная последовательность с этого спутника.
                                          Алгоритм генерации псевдослучайной последовательности:

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

                                          P.S. Я сначала начинал делать, поняв алгоритм именно как источник (и на используемом ЯП даже сходилось хорошо по формуле). Но на java всплыло, что pos/10 меняется раз в 10 шагов, что заставило, еще раз перечитав задание и комменты, поменять мнение о задаче.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              +1
                                              У меня для всех 7 последовательностей нашлись нужные смещения.
                                              Но пока не устраивает скорость и нет 100% уверенности в коде) Завтра будут все перепроверять и пробовать «ускорять».
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                  +1
                                                  (thedigest[0] >> 4) & 0x0F > 7
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                      +1
                                                      md5 выдает 128 бит (16 байт). Это 32 символа в hex.
                                                      Без наложения маски у вас в symbol получается значение первых двух символов строковой записи хеша.
                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                          0
                                                          У меня методом исключения '7' (7 в кавычках) вышло именно так. Символ как аналог байта + в кавычках + 7 как экватор интервала в 16.
                                                            0
                                                            И как, правда получилась последовательность, как в примерах? У меня упорно другая выходит.
                                                              +1
                                                              Да, получилась. И даже дистанции весьма похожие выходят.
                                                                +1
                                                                На test1 ошибка вышла в 85 метров, на test2 (пока что по первым двум спутникам из набора) ошибка в 8 метров. Так что вроде как подходит последовательность.
                                                              0
                                                              --промахнулся--
                                                                0
                                                                --промахнулся--
                                                            0
                                                            А не проще ( 0xFF & thedigest[0] ) > 0x70
                                                            Зачем лишний сдвиг.Только у меня всё равно не получается последовательность, как в примере.
                                                              0
                                                              Проще, но при этом вы допускаете ошибку.
                                                                +1
                                                                Вижу :) 0x7F там
                                                            0
                                                            У меня как у Vayun, разве что наложение маски и сдвиг в обратном порядке. Что не существенно.

                                                            Просто наложение маски дает в результате первые два символа md5hex.

                                                      +1
                                                      Да, вы правы — тут было не вполне ясно написано.
                                                      Я подкорректировал описание, надеюсь сейчас все стало понятнее.
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                +2
                                                со скоростью передачи 1 Мегабит (миллион бит в секунду), сигнал мы принимаем с частотой 10 миллионов выборок в секунду.
                                                Псевдослучайная последовательность повторяется каждую секунду.

                                                Я правильно понимаю, что длина последовательности которую передает спутник равна одному миллиону бит? Но если
                                                pos — изменяется от 0 до 9999999.

                                                то в итоге получается 10 миллионов бит? Или генерируется 10 Мбит, но передается только первый 1 миллион бит?
                                                  0
                                                  Смотрите подкорректированное описание последовательности, думаю сейчас должно стать понятнее.
                                                  +7
                                                  Читаю комментарии и понимаю, что я понимаю все меньше…
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                      0
                                                      То есть, каждый спутник пушит одинаковую последовательность?
                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                          0
                                                          FDMA коды у Глонасс — также используют одинаковую последовательность, но там правда еще модуляция добавлена, чтобы передавать данные со спутников.

                                                          Изначально я думал сделать CDMA — но это думаю отпугнуло бы слишком много людей.
                                                      0
                                                      Господа, это я глупый (я, честно — с горы у пал, сотрясение, ушибы, сижу болею), или что-то не так?
                                                      В условиях отсутствия помех, задача сводится к поиску опорного участка из 1М заранее известной выборки (сразу приводим 10М к 1М, т.к. нет помех и границы интервалов известны, а внутри-интервальный фазовый сдвиг сразу определяем по первому интервалу)? Что, очевидно, может быть сделано не более чем за один проход выборки спутника с максимальной точностью? Т.е. однократный проход трёх первых спутников всегда даёт максимальную точность, положения, которая упирается в точность double-арифметики?
                                                      P.S. Никто не хочет скооперироваться с java-гуру инвалидом?
                                                        0
                                                        И очевидно, что нужно отбирать максимально-удалённые друга от друга спутники до декодирования.
                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                            +1
                                                            ;)
                                                            Ну, прежде всего, если у нас всегда суперсэмплинг 1:10, то субинтевальный сдвиг (в пределах 10 бит входной последовательности) находится по первому изменению сигнала — так?
                                                            Дальше. Про разрешение сдвига — мне врачи много думать запретили, но опыт-то не пропьёшь :)
                                                            На кой чёрт Вам сдвигать всё? Рассказываю алгоритм оптимального поиска:
                                                            Берёте кодирующую последовательность (то, что md5 выдаёт, но без десятикратного повтора каждого интервала).
                                                            Находите максимальную по длине последовательность единиц и нолей — берёте то, что встречается меньше. Выбираете одну. Это опорная точка.
                                                            У нас всего 1М отсчётов ЗАРАНЕЕ ИЗВЕСТНОЙ кодирующей последовательности. Что смешно и мало.
                                                            Берёте контекст после опорной точки — некоторое количество бит, делающее последовательность уникальной в пределах кодирующей.
                                                            А теперь задача поиска фазового сдвига сводится к поиску длинной последовательности нолей/единиц (коих мало и делается быстро) и последующему сравнению короткого контекста — если контекст совпал, то опорная точка найдена и сдвиг известен с максимальной точностью. Если не совпал — продолжаете поиск длинной последовательности.
                                                            Это максимальной-возможно быстрый алгоритм, который ещё и абсолютную точность даёт.
                                                            Могу рассказать, как быстро искать контекст — практически со скоростью чтения массива памяти :)
                                                              0
                                                              Т.к. последовательность заранее известна всё становится весьма скучно.

                                                              При чтении из файла на лету кодируем в RLE. В таком представлении в этой конкретной последовательности есть 28 уникальных 2х-байтовые кусков. Если сделать табличку, то можно гарантированно находить смещение просмотрев худшем случае только 23% последовательности.
                                                                0
                                                                А если уникальные куски будут начинаться с длинной последовательности, то сравнение ещё упрощается. И нет смысла, несколько опорных точек искать — всё равно, скорее всего, нужно будет отсекать «лишние» спутники, а для этого нужно читать весь файл. При таком кодировании расходами на поиск опорной точки можно пренебречь — расходы на файловый ввод/вывод и декодирование будут больше. Соответственно, искать фазу по одной точке всегда.
                                                                И 2 байта для java плохо. Лучше int (4 байта), т.к. он там быстрее.
                                                                И лучше RLE-NZ — не различать ноли и единицы — уникальность не потеряется, т.к. всё равно можно использовать int или long, т.к. в java они быстрее работа. И класть результат RLE в тетрады.
                                                                  0
                                                                  RLE-NRZ, а не NZ, конечно же.
                                                                0
                                                                Ну вот, коллега, вы раскрыли все мои карты! :) Аналогичный алгоритм уже сейчас у меня дает 50мс на спутник на i5 в один поток. Теперь, наверное, введут ограничение и требование вводить для каждого спутника salt, мешающий проанализировать последовательность до начала работы.

                                                                P.S. Уважаю программистов старой закалки, которые не начинают работу, пока не выстроят всю логическую цепочку в голове.
                                                                  0
                                                                  Как-то медленно — нужно кэшированием чтения, чтением из файла, кодированием данных поиграться. Кстати, крайний случай, когда сдвиг практически равен длине последовательности и происходит «заворот» маркера, не забыли обрабатывать и отладить?
                                                                    0
                                                                    Делаю чтение из файла сразу с проверками, без кеширования данных. Возможно, если пускать файл через stdin и поиграться с буферами, то будет чуть быстрее. Ну и я не уверен в скорости Java 1.6 на Mac OS X vs 1.7 на Windows. «Заворот» обрабатываю тем, что ищу сразу два паттерна — 19 единиц и 18 нулей. «Разрезана» может быть только одна из них, а т.к. находятся они в последовательности очень удачно (одна в первом миллионе, другая в седьмом), то никогда не приходится перебирать целиком весь массив при корретных вводных данных. Из логичных оптимизаций еще напрашивается сделать поиск промежуточных паттернов и многопоточную обработку. Но вообще, положа руку на сердце, соревноваться «кто быстрее найдет паттерн в массиве» как-то не спортивно, изначальная задача наверняка подразумевала, что сколько-то вызовов md5 прийдется сделать во время работы.
                                                                      +1
                                                                      Даже если последовательность неизвестна достаточно будет посчитать rolling hash, и пробежаться от начала до конца. Правда в таком случае с двумя спутниками уже ничего не найдешь.
                                                                        0
                                                                        А причём два спутника? rolling hash мне в голову приходил, но мне показалось, что его реализация будет не быстрее поиска по патерну.
                                                                          +1
                                                                          Потому что если не знать исходной последовательности, то задержки сигнала находятся не абсолютные, а относительные. Время становится третьей неизвестной (в дополнение к двум координатам), соответственно нужно минимум 3 спутника чтобы всё вычислить.
                                                                            0
                                                                            Это будет совсем другая задача с совершенно иным способом решения. Она решается, грубо говоря, «аналоговыми» методами через интегрирование последовательности и разность фаз. Плюс, последовательное приближение точности результата в зависимости от времени вычисления, практически до бесконечности.
                                                                        0
                                                                        Я имел в виду BufferedInputStream. Мне кажется, что поиск одной последовательности будет быстрее. А если последовательность не найдена, то она разрезана — обрабатывать отдельно, но это крайне редкий и, скорее всего, не возможный случай.Дело в том, что если правильно всё написать, то бОльшая часть затрат времени всё равно уходит на чтение и декодирование файла, так что имеет смысл делать максимально-быстрый поточный алгоритм, а это значительно быстрее с одним патерном.
                                                                        И это только половина дела. Наверное даже меньшая. Там дальше танцы с поиском оптимального набора спутников, либо огород с обработкой данных сразу от всех спутников (кстати, это два совершенно разных пути). И ещё приседания с точностью, так как во множетсве случаев всё упирается в точность double, но, по-моему, оно решается подбором очерёдности расчёта и коэффициентов.
                                                                          0
                                                                          Использую BufferedReader. Не удивлюсь, если само чтение из файла и занимает 49.9 мс из 50. В таком случае поиск нескольких паттернов может быть полезным из-за более раннего выхода из цикла. Проверим.
                                                                          И это только половина дела. Наверное даже меньшая.

                                                                          Вот это уже добавляет интереса в соревнование. Завтра попробую несколько вариантов, тут есть разные хитрости, особенно с учетом использования i7-3820 c HT, т.е. с 8ю потоками.
                                                                            0
                                                                            Ранний выход, это хорошо, но файл всё равно должен быть прочитан весь, так что ранний выход даёт мало относительного прироста — я именно это имел в виду. И кстати, русских букв в файле быть не может, так что самописное чтение файла, как байтового потока, с самописным выделением строк и особенно декодированием строк последовательности даст значительный прирост. Стандартные функции чтения имеют значительный оверхед на работу с кодировками символов и перекодированием UTF16. Да и с буферами там сложности. При самописном же чтении можно обойтись одним байтовым буфером на ткущую строку в 10М+2 символов и работать прямо в нём.
                                                                              0
                                                                              А зачем файлу быть прочитанным целиком, если нам известен размер каждого блока +-10 байт? Это ведь две мантиссы с экспонентами + 10кк цифр, можно с помощью различных seek сразу выделить каждому потоку нужный сегмент файла, вернее, System.in потока. Тут как раз будет важно первым заходом получить примерные координаты по 2-4 спутникам (по количеству ядер) и следующим шагом выбрать максимально удаленные, если временная квота позволяет. А вот работа сразу с byte это хорошая мысль, спасибо. Активно использую это в Nomad Reader, а тут как-то сразу не пришло в голову.
                                                                                0
                                                                                Если хочется максимальной скорости любой ценой, то readAllBytes и вперед парсить вручную. На Си на один спутник уходит ~1мс, так что улучшать есть куда)
                                                                                  0
                                                                                  Боюсь, при всем желании, мой винчестер только в 2063м году сможет выдавать 10 мегабайт данных за 1мс, т.е. 10 гигабайт в секунду :) А так, в памяти у меня тоже 1мс поиск занимает.
                                                                                  0
                                                                                  Не верно. Вы не учитываете, как оно на более низком уровне работает — библиотеки и ОС. Подобная оптимизация только только замедлит. А seek это вообще адово медленная операция. По ка вы seek сделаете, я уже последовательность прочитаю.
                                                                                  Мне кажется, что нет смысла примерные координаты считать — имеет смысл читать всё, либо делать отсечку по количеству спутников (если спутников много), а потом отбор по используемым спутникам сделать. Расчёт координат как раз мгновенно на фоне всего остального будет. А вот выбор спутников для расчёта будет соизмерим со временем чтения файла и поиска фаз.
                                                                                    0
                                                                                    Ну как же так, коллега? На среднестатистическом винчестере с 100мб/с вы будете 100 спутников считывать порядка 10 секунд. А если их будет 200, 500? Последовательно разумно читать 3-5 спутников по 10мб, затем делать их анализ, а параллельно прыгать по файлу через seek (даже если его вызов займет по 10мс на спутник, это примерная скорость для современных HDD) и выбирать наиболее полезные дополнительные спутники по координатам.
                                                                                    А если же подача данных через System.in означает автоматическое прекеширование входящих данных и замер скорости будет именно алгоритма, то вообще мы не о том говорим.
                                                                                      0
                                                                                      Данные гарантированно будут в дисковом кеше, чтобы тестировать решение а не диск (скорость его мне и так известна, 500Мб/сек).

                                                                                      Добавлено в описание.
                                                                                        0
                                                                                        Всё верно, если бы был файл, то используем MappedByteBuffer и читаем только то что надо. Но по условию всё читается из стандартного ввода, так что остается предполагать hot cache, иначе 99.9% времени будет занимать чтение входных данных и конкурс не имеет смысла)))
                                                                                          0
                                                                                          У меня сейчас даже с кешем получение stdin одним куском занимает больше времени, чем вся остальная работа. Скорость чтения в 900-1300МБ/с может и высокая, но недостаточно :)
                                                                                            0
                                                                                            Раз топикстартер сказал, что у его винта скорость 500Мб/с, то рассчитываем, что дисковый кеш в таком случае отдает еще в 5-10 раз быстрее. Иначе никак — stdin не позиционируемый поток, мы можем только скипать данные, даже параллельность тут ничего не даст.
                                                                            0
                                                                            ограничение есть на максимальное расстояние от центра координат в 6000км,
                                                                            на скорости света это задержка существенно меньше секунды, а значит хвосты от разных спутников будут гулять в районе начала последовательностей, и даже до середины не дойдут…
                                                                            Расстояние между спутниками даже такой задержки не дадут.
                                                                              0
                                                                              Если точнее, то максимальное расстояние между спутником и приёмником 20'000+6'378=26'378 км, это расстояние свет проходит за 0.0879875 секунды, а значит, максимальное смещение — 879'875 отсчётов, что, конечно, существенно меньше 10'000'000. Так что анализировать достаточно первый мегабайт, остальное можно скипать. Если читать все 10Мб, возможно, будет заметный провал в производительности: кэш третьего уровня в i7 только 8Мб.
                                                                                0
                                                                                Хотя нет, в i7-3820 10Мб кэша. Впритык может влезть.
                                                                        0
                                                                        Как быстро найти опорную точку? Ну, например кодировать входную последовательность (после деления кол-ва отсчётов на 10, конечно же) в RLE.
                                                                        Т.е. вместо единиц и нолей ставите их количество. Скорее всего единица там или ноль вообще не нужно знать. Количество уменьшаете на 1 закатываете 4-битную тетраду long-слова. Если единиц или нолей подряд больше 16, то пишете 16.
                                                                        Например:
                                                                        111011000111111 будет представлено, как 0x20125
                                                                        Жизненный опыт говорит, что при такой относительно короткой кодирующей последовательности будет существовать множество уникальных контекстов, помещающихся в слово long (16 изменений сигнала — это много) в таком кодировании.
                                                                        Дальше экодер преобразует входную последовательность в long-числа, а компаратор сравнивает с искомым контекстом, как сравнение чисел long на равенство. На каждом следующем шаге энкодер сдвигает начало сравниваемой последовательности к следующему изменению сигнала.
                                                                        Скорость получается адова.
                                                                          0
                                                                          Не дописал:
                                                                          А учитывая, что у нас искомый контекст начинается с длинной последовательности нолей/единиц, энкодер вообще на каждом шаге пропускает кучу данных, пока не встретится последовательность нужной длинны.
                                                                          Если в крации, то ищем окном с привязкой начала окна к длинной последовательности и кодированием NRZ-RLE
                                                                            0
                                                                            Чтобы не перебирать спутники и достичь максимальной точности ограничиваем кол-во используемых спутников, и отбираем те, которые образуют многоугольник максимальной площади. Естественно, до начала декодирования из сигнала.
                                                                            Т.к. с перебором многоугольников чёрт ногу сломит, то, например, ограничиваем кол-во спутников кратным трём и сводим задачу к поиску n-треугольников треугольников максимальной площади из заданного набора вершин. Сверху прикрутить оптимизацию и фильтрацию по-вкусу.
                                                                            6 или 9 спутников будут давать очень хороший результат, IMHO.
                                                                            0
                                                                            В условиях отсутствия помех достаточно данных любых двух спутников, главное определить сдвиг, только вот условия задачи несколько размыты, для определения этого сдвига.
                                                                              0
                                                                              Вон выше уже алгоритм расписан — чего размыто-то? Кроме того, если спутники далеко, то даже точное определение фазы даёт точность десятки метров. А если спутники рядом, то они дают две точки пересечения, плюс, точность падает до нескольких сотен метров. Т.е. нужно три и более спутников, отстоящих на максимальное расстояние.
                                                                              Всё упирается в перебор спутников и точность double-арифметики.
                                                                                0
                                                                                Два спутника дадут вам 2 возможные точки. В общем случае нужно 3 спутника.
                                                                            0
                                                                            А java 64-бита? А то сильно разные производительности в разных случаях у них.
                                                                              0
                                                                              Да, добавлено в статье.
                                                                              +1
                                                                              Как считается delta? Евклидово расстояние до правильной точки?
                                                                              +1
                                                                              В какую сторону округляется задержка времени при вычислении сдвига последовательности?
                                                                                0
                                                                                До ближайшего целого.
                                                                                0
                                                                                Будет ли промежуточное тестирование? Хотя бы на подмножестве тестов.
                                                                                  0
                                                                                  Так 2 теста лежат — берите и тестируйте :-)
                                                                                  Т.е. нет.
                                                                                    +1
                                                                                    В этих тестах неизвестно настоящее положение ответа (то есть нельзя посчитать delta) и нет параметров системы, на которой будет финальное тестирование (то есть нельзя посчитать время работы).

                                                                                    Ну и промежуточные результаты повысили бы интерес :)
                                                                                      +1
                                                                                      Согласен с вами, и думаю в следующий раз (если он будет) будет организовано предварительное тестирование при отправке.
                                                                                        +1
                                                                                        А по системе информация следующая: Java 1.7 64-бит, i7-3820 с HT, входные данные в дисковом кеше.
                                                                                          +1
                                                                                          Можете еще указать точный ответ для примеров?
                                                                                            0
                                                                                            Читайте новое дополнение к статье.
                                                                                            0
                                                                                            А что с памятью для Java? т.е. что-то вроде java -Xms512m -Xmx1g или дефолтный кошмар вроде -Xms32m -Xmx128m?
                                                                                              +1
                                                                                              Допустимо использовать до 30Гб памяти, -Xms10g -Xmx30g
                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                        +1
                                                                                        Этот тот тест, где в ответе ожидалось что-то вида "-1.81683e+006 -1.74334e+006"?

                                                                                        А то у меня там вышло
                                                                                        -1816744.990 -1743348.485 (погрешность 85.431)

                                                                                        Для кучи второй
                                                                                        3069326.513 -2594044.901 (погрешность 8.271)

                                                                                        Погрешность считал относительно значений в test*.out
                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                            0
                                                                                            Не особо как-то. Да и смещение в 529131, это примерно полсекунды передачи. Т.е. расстояние примерно в 299792.458/2 километров.
                                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                0
                                                                                                Уже ответил ниже Nomad1'у. У меня смещения считаются по другой длине последовательности, так что не стоит сравнивать их с вашими.
                                                                                              +1
                                                                                              да +- 30. Комментатору выше: 529131 это при скорости 10мбит это около 0.05секунды.
                                                                                                0
                                                                                                У меня смещения считаются по размеру исходной последовательности (1кк).
                                                                                              0
                                                                                              Не могу понять, как у вас вышла такая малая погрешность в первом варианте.

                                                                                              Повторю тест вручную:
                                                                                              1. Находим в test1.in через текстовый редактор нашу последовательность. Для первого спутника она в колонке 619127, для второго 529102
                                                                                              2. Вычисляем задержку в секундах для обеих спутников делением на скорость света и умножением на 10м через Wolfram Alpha, выходит 1.85609605144166E7 и 1.58620789112716E7 соответственно. Числа точные, потому как тут было только умножение.
                                                                                              3. Считаем точки пересечения. Тоже воспользуемся Вольфрамом. Результат: (-1.61583x10^7, 75872.4) | (-1.81668x10^6, -1.74336x10^6)
                                                                                              Первая точка вне пределов Земли, ее отбросим. Остается "-1.81668e+006 -1.74336e+006", что дает нам Delta = 151.327, т.е. ~151 метр. Программа у меня высчитала с double точностью точку с дельтой 156, но я не понимаю, как там можно было получить 85. Допустим, можно было бы сказать, что у вас более точная константа c, но с 1983 года изменено определение метра и теперь это 1/299792458 от скорости света. Других теорий у меня не осталось
                                                                                                +1
                                                                                                У меня другие смещения высчитываются.
                                                                                                А расстояния, соотвественно, 18560930.535 и 15862048.932. Близко к вашему варианту, но другие.

                                                                                                P.S. Со скоростью света у меня все ок :)
                                                                                                ... (double)299792458 ...

                                                                                                  0
                                                                                                  Ага! В текстовом-то редакторе колонки не с нуля считаются, а с 1 :) Значит и смещения на единичку меньше должны быть. Это я заработался уже. Спасибо!
                                                                                                    0
                                                                                                    Вообще, у меня ЗНАЧИТЕЛЬНО другие смещения :) Мы же уже обсуждали несколькими комментариями выше, что у меня смещение ищется в 1кк последовательности, а не в 10кк. А для 1кк смещение в 500к — это полсекунды отставания. В примере test1 у меня смещения далеко за 900к перевалили.
                                                                                                      0
                                                                                                      Одно другому не мешает. Я разделил ваше число 18560930.535 на 299792458 и получил 52,91009999991394. Если присмотреться, то это 529101, отличающееся от моего 529102 аж на единицу. Поправил, стало все гораздо лучше.
                                                                                                0
                                                                                                Аналогично — что-то хреновата точность.
                                                                                                0
                                                                                                Для третьего тестового набора (3_hi_precision) пока что так:
                                                                                                3420804.238 -1950286.68 (погрешность 11.906)
                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                    0
                                                                                                    Расстояние между найденной мною точкой и точкой, координаты которой указаны в соответствующем test*.out.
                                                                                                0
                                                                                                Я хотел бы выразить несогласие с ответом из test1.out.
                                                                                                Значение -1.81683e+006 -1.74334e+006 это одна из точек пересечения окружностей, образованных идеальными радиусами двух спутников (на картинке справа). В более-менее реальной гео-локационной задаче если у нас только два спутника, то логично было бы взять среднюю точку между двумя пересечениями, а не одну из крайних. Вопрос звучит так: стоит подогнать результат под тестовый пример (т.е. взять одну из этих точек), либо можно использовать в такой ситуации центральную точку?

                                                                                                картинка

                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                    0
                                                                                                    Ну так может подразумевалась любая из двух точек пересечения? и если я вставлю туда среднюю точку, то не пройду простейший тест из 2х спутников :)
                                                                                                      0
                                                                                                      Я беру все подходящие точки (в вашем случае их две) и считаю среднее положение. Опять же в вашем случае получится как раз средняя точка.
                                                                                                        0
                                                                                                        Ну так тогда должно получиться что-то такого типа, а не данные из test1.out:
                                                                                                        Point: -1.6158743300763596E7, 75910.49328442
                                                                                                        Point: -1816255.2695345273, -1743428.8960310156
                                                                                                        Result: -8987499.0, -833759.2
                                                                                                        
                                                                                                          0
                                                                                                          Заранее известно, что приемник гарантированно находится не далее 6378км от начала координат.

                                                                                                          P.S. Я специально написал выше «подходящие точки», так как произвожу фильтрацию всех пересечений плюс последующую кластеризацию. И только по оставшимся уже считаю центр.
                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                    +1
                                                                                                    Я уже передумал — точность и скорость показались важнее. Рука не поворачивается писать плохой код и использовать заводские readLine там, где важна каждая миллисекунда.
                                                                                                      0
                                                                                                      У меня пока ~10К и еще может немного меняться в любую сторону немного.
                                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                          0
                                                                                                          Круто. А я не настолько хорошо знаю java и ее стандартную библиотеку, чтобы пытаться минимизировать код.
                                                                                                      +1
                                                                                                      > В случае, если однозначное вычисление координат невозможно — допустимо вывести любое из решений.
                                                                                                      Означает ли это что в случае двух спутников правильных точек будет две и delta будет равна расстоянию до ближайшей из них?
                                                                                                      0
                                                                                                      А если есть одна связная область из допустимых точек, в которой существуют две точки, удалённые более чем на 1 км или, вообще, не существует точки, максимальное удаление до которой меньше 1 км, то ответом считать любую точку из этой области?
                                                                                                        0
                                                                                                        Ответом можно считать вообще любую точку на земле. Вопрос лишь в ошибке, и будет ли ответ с такой ошибкой засчитан.
                                                                                                        Ошибка рассчитывается до ближайшей «идеальной» точки, полученной геометрическим образом на основе знания идеальных, не округленных параметров задачи.

                                                                                                        Т.е. обеспечить ошибку 0 вы не сможете, но можете уменьшить математическое ожидание ошибки.
                                                                                                          +1
                                                                                                          Если разместить два (да хоть двести два) спутника внутри окружности радиуса один метр, область допустимых решений будет представлять собой здоровое слегка деформированное кольцо и шансов попасть рядом с правильным решением будет крайне мало, хоть какую мегаматематику применяй. Есть надежда, что набор тестов не содержит подобных невменяемых конфигураций :-)
                                                                                                            0
                                                                                                            lany дело говорит, в общем случае невозможно написать программу, проходящие все возможные тесты хоть с какой-то вменяемой вероятностью. Это печалит, потому что не понятно, где проводить границу между «сложный тест» и «ну, такого в тестах не будет». Это особенно важно для тех, кто пишет mincode, потому что точность для этих участников не главный приоритет, а значит им нехорошо просто говорить: «сделай как можно лучше».
                                                                                                              0
                                                                                                              Вам не нужно пройти все возможные тесты с очень маленькой ошибкой, вам достаточно пройти их лучше конкурентов :-)

                                                                                                              Но ваши чувства я понимаю — в 99% олимпиадных задач приучают именно к математически строгому идеальному решению.
                                                                                                              В жизни же обычно получается как в этой задаче…
                                                                                                                +1
                                                                                                                Проблема не в идеальности/не идеальности, а в невозможности пройти предложенный lany тест. С этой фразой факт невозможности попасть в +-1км плохо соотносится: «за самое компактное решение, проходящее все тесты (по времени и требуемой точности) 1 BTC.» То есть, если составить сильный набор тестов, то в этой номинации просто не будет победителя.
                                                                                                                  0
                                                                                                                  Да, тут вы правы.
                                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                            +1
                                                                                                            С тем что был факап я согласен — правда в другом месте, с округлением координат. Это существенно усложняло задачу и делало её намного более мутной — и это пришлось исправить через день после начала с изменением тестов.

                                                                                                            А в случае с генерацией последовательности — это обычное дело, на соревнованиях постоянно кто-то фиксируется на своем понимании какого-то нюанса условий и не может вырваться — это самые сложные для нахождения ошибки. Даже если бы я сказал «первые 4 бита» или даже «первый бит хэша» — все равно остался бы вопрос «big endian» или «little endian», требовавший бы проверок различных вариантов.
                                                                                                              +2
                                                                                                              На MD5 вообще наплевать. Задача могла формулироваться как «берётся некая последовательность, которая неизвестно как сгенерирована, но всегда постоянная». Её же можно из любого сэмпла вытащить. Надо только взять известный output, посчитать радиусы и смещения. Зачем над этим биться часами — вообще не понимаю.
                                                                                                              0
                                                                                                              А после завершения будут опубликованы все или хотя бы некоторые решения?
                                                                                                              Мне вот лично было бы весьма интересно посмотреть на лучшие решения да и вообще на подходы к решению задачи.
                                                                                                                +1
                                                                                                                Судя по прошлому соревнованию — да.
                                                                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                  0
                                                                                                                  Я целился, а что?
                                                                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                      +3
                                                                                                                      863 :P Правда, считывание у меня очень чувствительное на изменение формата ввода.
                                                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                          +1
                                                                                                                          Update 10.05.2014 2:03: Подкорректировано описание кодовой последовательности. Выполнятся будет на 64-битной Java (-Xms10g -Xmx30g). Переводы строк — не документированы, лучше на это не закладываться.
                                                                                                                        0
                                                                                                                        1678. Пытался за двумя зайцами угнаться: сделать и компактное, и точное решение. Боюсь, ни одного не поймаю.
                                                                                                                      +1
                                                                                                                      Чтобы показать, что компактность кода это бред (оценивать надо не кольчество символов, а результирующий байткод), я послал две версии — на 6000 байт, с комментариями, нормальными названиями, стилем и пр., и ее же, минифицированную до нечитаемости и размера чуть менее 3кб. Выкинуты все лишние пробелы, переносы строк, комменты, константы, сокращены переменные до 1-2 букв. Код из читабельного и реюзабельного стал «черным ящиком». Если кто-то в команде будет писать в таком стиле, то я первый отгрызу ему руки. Надеюсь, что всеобщее безумие с «ЦУП в 30 строк» и подобные номинации рано или поздно сойдут на нет.
                                                                                                                      Для сравнения, недавно товарищ писал мультиметр для AVR на C, но пытался обойти без флоатов и sprintf/dtostr, чтобы вместиться в 8кб памяти. В программе можно было написать десяток строк без существенного изменения бинарника, но dtostr(amp * 1.257f / 10000.0f) добавляло сразу 2кб к результату. На собственные супер-оптимальные ftoa/ioa и целочисленные вычисления без вспомогательных классов ушла львиная часть времени, но в результате и код читабелен, и размер проги после компиляции около 4кб.
                                                                                                                        0
                                                                                                                        Байткод сравнивать тоже под вопросом. Если компилируется на стороне проверяющего, то возникает вопрос, какие ключи используются: вставлять ли информацию о номерах строк и именах локальных переменных. По дефолту она есть, и тогда ужимание в одну строку и использование однобуквенных переменных всё равно уменьшит результат. Но если даже отключить всю отладочную инфу, в пул констант лягут имена полей и методов (они в любом случае должны быть доступны в рантайме, ибо рефлекшн), поэтому их тоже конкурсанты будут сокращать. Могут проводиться и другие странные оптимизации: например, использование
                                                                                                                        String.valueOf(x).concat(" ").concat(String.valueOf(y))
                                                                                                                        
                                                                                                                        даст более короткий байткод, чем x+" "+y, но на читаемости скажется не лучшим образом.
                                                                                                                          0
                                                                                                                          Ключи обсудить заранее вообще не проблема. Поля и методы в минимальном коде тоже будут минимальными, без вложенных классов и дженериков.
                                                                                                                          А вот читабельность это отдельный вопрос — ваш пример с x + " " + y во-первых очень просто описать людским языком в комментах (к тайм-критикал коду так вообще часто делается), во-вторых, в некоторых случаях будет скомпилирован в такой же байт код (в гипотетическом Java 15 или другом рантайме), а в-третьих, еще быстрее и компактнее будет в виде StringBuilder, который вполне читабелен.
                                                                                                                            0
                                                                                                                            Почему быстрее и компактнее в виде StringBuilder? Именно StringBuilder и будет создан по дефолту из x+" "+y. Эта строка в байткоде превратится в new StringBuilder().append(x).append(" ").append(y).toString(). Не факт, что это будет быстрее и уж точно не компактнее, чем два concat'а. От рантайма это вроде как не зависит, а на некоторые гипотетические случаи странно закладываться: в конкурсе подразумевается конкретная версия Java. В Java 15 наверняка будут свои способы извратиться с целью сократить байткод.

                                                                                                                            Я всё к тому, что идея оценивать результирующий байткод тоже не идеальна в плане получить красивое приложение. Опять же я в своём решении пользовался вложенными классами (правилами это не запрещено). Для них будет создан отдельный .class-файл со своим констант-пулом, где куча констант будет пересекаться с константами главного класса. Это сразу существенно удлинняет суммарный размер сгенерированных .class-файлов. Если бы я добивался наименьшего размера .class-файлов, я бы, естественно, запихал всё в один класс, пожертвовав структурированностью.
                                                                                                                              0
                                                                                                                              С SB будет 4 вызова функции, как и с конкатами. Будет ли лишний промежуточный класс создаваться — хз, наверное будет. И, думаю, будет работать быстрее за счет отсутствия переаллокаций. Можно перепроверить, но это не критично, я к тому, что экономия в пару байт, еще и в ущерб скорости, еще и та, что могла бы быть изначально оптимизирована компилятором — очень сомнительное место. Нормальный человек так делать станет лишь если это очень-очень-очень нужно. В случае же «компактного кода» реально на конкурс получить программу в один метод и 3-5 длинных строк с goto, однобуквенными переменными и пр. — такой себе аналог байткода.
                                                                                                                                0
                                                                                                                                О, вызовы функции — это мелочи, а вот промежуточных объектов там немало. Дефолтная аллокация 16 байт, для результата из нашей задачи переаллокация будет почти наверняка. Конкаты безусловно выгоднее, если вам надо миллион раз склеить строки попарно. А если с конвертацией чисел в строку и по три — тут я не уверен. Так или иначе, а разница в быстродействии в любую сторону совершенно эфемерна, если эта строчка выполняется один раз: её будет абсолютно не видно на фоне погрешности измерений. Это надо правильный микробенчмарк делать с разогревом. А вот экономия байт в класс-файле с конкатом существенная: речь идёт о десятках байт. Можете сами проверить. Если б я участвовал в конкурсе на минимальный размер .class-файла, я бы безусловно вставил конкаты. Естественно, в реальном коде я бы так не делал. Поэтому конкурсный код с минимизацией хоть исходника, хоть .class-файлов будет выглядеть ужасно, это в любом случае изврат. Думаю, все понимают разницу между программированием на конкурсе и реальным программированием :-)
                                                                                                                                  0
                                                                                                                                  Если гнаться за размером class-файла, то стоит задуматься о том, что бы писать сразу на ассемблере.
                                                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                        +4
                                                                                                                        Видимо вторник понятие растяжимое :)
                                                                                                                          +5
                                                                                                                          Ну BarsMonster же не сказал, какой конкретно вторник имеется в виду :-)
                                                                                                                            +2
                                                                                                                            Lol :-)
                                                                                                                            Да, работа над результатами завершается, в ближайшие часы будет опубликовано.

                                                                                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                                                    Самое читаемое