Вы идеализируете хеш-таблицы. Даже если ваша хеш-функция идеальна, то чтобы избежать коллизий, под таблицу надо отводить в несколько раз больше памяти, чем в ней будет записей. К тому же, надо эти самые хорошие хеш-функции вычислять. Отсюда и вылезает довольно ощутимая константа в этой вашей асимптотике. А логарифм не так уж быстро растет.
Поэтому не исключено, что решение с сортировкой более практичное. И как вам указали выше, вариант с сортировкой хорош тем, что его можно реализовать out-of-core, если использовать, например, merge sort. Представьте, например, что каждый из списков занимает 100 ГБ.
Только вот надо сказать, что декодер, работающий по такой приближенной формуле, довольно сильно проигрывает по вероятности ошибки «настоящей» формуле. Настоящая формула выглядит так:
x = 2 * atanh(tanh(a/2) * tanh(b/2)),
где a и b — настоящие LLR (т.е., не квантованные в int). К сожалению, в таком виде формула очень медленная и численно неустойчивая. Поэтому умные люди придумали эквивалентную ей формулу:
Как видно, здесь все упирается в вычисление функции log(1 + exp(-abs(t))) для разных значений t. Для нее приходится делать lookup table. Работает это дело относительно медленно — уже не так важно, как вы там вычисляете максимум.
Интереснее, как оптимизировать другую половину алгоритма (на variable nodes). Там приходится «обрезать» получающиеся суммы, чтобы они не выходили за пределы некоторого интервала [-N, N], т.е. примерно так: x = max(min(a, N), -N). Вот тут битовые ухищрения у меня работали медленнее, чем условные переходы.
Зачем здесь брать модуль? Если вы возьмете две точки на одном меридиане, но с противоположными широтами, то ваша формула будет считать их за одну точку и вернет ноль в качестве расстояния.
Кроме того, вот тут модуль тоже не нужен:
COS(ABS(dst_lat) * PI()/180)
поскольку косинус — четная функция, т.е. cos(x) = cos(-x).
Вроде бы только второй год проводится. Организатор — Университет Чикаго, в котором все это и проходило. Основной спонсор в этом году — Palantir. Вот сайт мероприятия: icpc.cs.uchicago.edu/invitational2013/
Там, кстати, лежат задачи с тестами. И фотографии.
Интересно было бы удаленно поучаствовать, задним числом. Будет ли доступно дорешивание в интернете, или хотя бы условия с тестовыми данными? Не помешала бы нам такая тренировка.
Кстати, аналогичное мероприятие в Америке было в конце марта в Чикаго, помещение выглядело вот так.
Я вот тоже школьник, правда в 8-ом классе, нахожу такие олимпиады, ИМХО, бесполезными, максимум забавными.
…
Сколько бы те несостоявшиеся программисты-математики говорили о важности спортивного программирования как такового, этот факт остется преувеличенным
Вы меня простите, но это просто ваша ограниченность и невежество (спишем это на ваш возраст).
Олимпиадные задачи не учат писать правильный код. Но, действительно, они учат думать. Благодаря олимпиадным задачам вы можете хорошо познакомиться с классическими алгоритмами и впитать в себя их идеи.
Многие из этих алгоритмов действительно не часто могут пригодиться на практике. Особенно если вы собираетесь всю жизнь программировать пользовательские интерфейсы и подобное. Если же вы собираетесь заниматься чем-то более серьезным, без знания классики вам будет тяжело. Сходите, например, вот сюда и решите задачи Nearby и Typeahead Search. Вполне себе олимпиадные задачи, имеющие прямое практическое приложение.
Да и дело не только в прямом практическом применении. Это спор из серии «нужна ли математика программисту». Конечно, напрямую часто она не нужна. Программисту даже родной язык в принципе не нужен, ему достаточно разговаривать на C++. Это просто вопрос общей образованности.
Никто не спорит, что на практике не менее важно уметь писать чистый, хорошо спроектированный код. Также важно разбираться в технологиях и все такое. Но, поверьте мне, всё это — ремесло, а не наука. Это приходит с опытом и дело нехитрое, если есть голова на плечах. Понимание математики и алгоритмов просто так с опытом не приходит, и упускать шанс их изучить, участвуя в олимпиадах — глупо.
Если умеете быстро читать по-английски и регулярно смотрите англоязычный youtube или фильмы, то вполне возможно — проверено на собственном опыте. Главное хорошо представлять, что такое этот самый TOEFL. Очень помогают пробные экзамены, которые продаются на компакт-дисках вместе с толстыми такими книжками — в интернете можно наверняка купить полностью электронную версию, ну или заторрентить, кому совесть позволяет :).
А как будет происходить удаление объектов в вашем примере? Есть ли в Objective C сборщик мусора, или же NSMutableArray позаботится об этом?
В C++ тоже можно написать просто вот так:
std::vector<File*> files;
File* file = new File("file1.txt");
files.push_back(file);
и никаких вспомогательных сущностей не надо. Вопрос только в том, кто будет эти объекты потом удалять. Можно либо воспользоваться аналогом vector, который делает это автоматически, либо удалять вручную, либо прикрутить к C++ сборщик мусора.
Насколько я понимаю, если мы не изменим that, ничего не выйдет: в that останется ненулевой handle, который будет закрыт в деструкторе, в результате чего в this окажется указатель на уничтоженный FILE.
Для реализации вычислений над конечными полями, которые используются, среди прочего, в теории кодов, исправляющих ошибки (см., например, Коды Рида-Соломона, используемые при записи данных на компакт-диски и еще много где).
Сама идея сходна использованию логарифмов: вместо умножения двух вещественных чисел можно складывать их логарифмы (именно на этом основан принцип работы логарифмической линейки).
Поэтому не исключено, что решение с сортировкой более практичное. И как вам указали выше, вариант с сортировкой хорош тем, что его можно реализовать out-of-core, если использовать, например, merge sort. Представьте, например, что каждый из списков занимает 100 ГБ.
где a и b — настоящие LLR (т.е., не квантованные в int). К сожалению, в таком виде формула очень медленная и численно неустойчивая. Поэтому умные люди придумали эквивалентную ей формулу:
Как видно, здесь все упирается в вычисление функции
log(1 + exp(-abs(t)))для разных значений t. Для нее приходится делать lookup table. Работает это дело относительно медленно — уже не так важно, как вы там вычисляете максимум.Интереснее, как оптимизировать другую половину алгоритма (на variable nodes). Там приходится «обрезать» получающиеся суммы, чтобы они не выходили за пределы некоторого интервала [-N, N], т.е. примерно так: x = max(min(a, N), -N). Вот тут битовые ухищрения у меня работали медленнее, чем условные переходы.
Зачем здесь брать модуль? Если вы возьмете две точки на одном меридиане, но с противоположными широтами, то ваша формула будет считать их за одну точку и вернет ноль в качестве расстояния.
Кроме того, вот тут модуль тоже не нужен:
поскольку косинус — четная функция, т.е. cos(x) = cos(-x).
Там, кстати, лежат задачи с тестами. И фотографии.
Кстати, аналогичное мероприятие в Америке было в конце марта в Чикаго, помещение выглядело вот так.
Вы меня простите, но это просто ваша ограниченность и невежество (спишем это на ваш возраст).
Олимпиадные задачи не учат писать правильный код. Но, действительно, они учат думать. Благодаря олимпиадным задачам вы можете хорошо познакомиться с классическими алгоритмами и впитать в себя их идеи.
Многие из этих алгоритмов действительно не часто могут пригодиться на практике. Особенно если вы собираетесь всю жизнь программировать пользовательские интерфейсы и подобное. Если же вы собираетесь заниматься чем-то более серьезным, без знания классики вам будет тяжело. Сходите, например, вот сюда и решите задачи Nearby и Typeahead Search. Вполне себе олимпиадные задачи, имеющие прямое практическое приложение.
Да и дело не только в прямом практическом применении. Это спор из серии «нужна ли математика программисту». Конечно, напрямую часто она не нужна. Программисту даже родной язык в принципе не нужен, ему достаточно разговаривать на C++. Это просто вопрос общей образованности.
Никто не спорит, что на практике не менее важно уметь писать чистый, хорошо спроектированный код. Также важно разбираться в технологиях и все такое. Но, поверьте мне, всё это — ремесло, а не наука. Это приходит с опытом и дело нехитрое, если есть голова на плечах. Понимание математики и алгоритмов просто так с опытом не приходит, и упускать шанс их изучить, участвуя в олимпиадах — глупо.
В C++ тоже можно написать просто вот так:
и никаких вспомогательных сущностей не надо. Вопрос только в том, кто будет эти объекты потом удалять. Можно либо воспользоваться аналогом vector, который делает это автоматически, либо удалять вручную, либо прикрутить к C++ сборщик мусора.
Сама идея сходна использованию логарифмов: вместо умножения двух вещественных чисел можно складывать их логарифмы (именно на этом основан принцип работы логарифмической линейки).