Открыть список
Как стать автором
Обновить

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

Видеокарты можно использовать?
Нет, только CPU.
А разве эта задача может быть эффективна решена на GPU?
Вот это я и хотел выяснить, если б можно было использовать GPU.
А есть ли смысл обрабатывать на GPU несколько последовательностей в МБ-ГБ весом?
В память все не засунуть, гонять по шине — не большое удовольстве. Только со значительной предобработкой на том же CPU…
НЛО прилетело и опубликовало эту надпись здесь
Да, в этот раз только студенты и закончившие в прошлом году. Либо можно поучаствовать в качестве руководителя команды. В общем, там на форуме писали варианты :)
В конкурсе могут принимать участие команды из 1 или 2 человек. Все участники конкурса должны быть студентами (включая аспирантов) или выпускниками 2011 года.
Как я понял объяснения Бориса, можно «шествовать» над командой, делясь опытом и советами с разработкой. Но не делать за них. Т.е. что-то типа преподавателя в учебном заведении, помогающему талантливым ученикам.
Как к этой возможности поучаствовать можно привести курсы онлайн не представляю.

Я вот и не студент и знакомых таких нет. Так что являюсь сторонним независимым наблюдателем :)
А вы давно закончили учиться? Думаю, можно зарегистрироваться, указав вуз, который закончили, и попробовать поучаствовать.
Можно, приходите, будем рады :)
Можете обновить дату на странице? А то там стоит 20.02, кажется, будто уже опоздал.
Про какую страницу вы говорите?
Спасибо, скрыл дату, она не имеет смысла.
В архиве с примером в readme отсылка на французский сайт. Это международный конкурс?
Конкурс проводится отдельно для России+СНГ и для региона EMEA (Европа, Средняя Азия, Африка). Задача в обоих регионах одинаковая, но призы будут выдаваться независимо.
Так что да, конкурс международный, на главной странице справа есть ссылки на Английскую, Французскую и Немецкую страницы конкурса.
Получил посылку от Intel c Поло и внутри было две брошюрки на участие в данном конкурсе. Пойду завтра кину в педагогический информатикам и в Дальневосточный Федеральный универ.
Спасибо, когда я клал листовки в посылку для вас, я знал, что они не пропадут ;)
Для тех, у кого еще нет ультрабука и SSD-диска:
1. берем книгу «The Algorithm Design Manual» by Stiven S. Skiena
2. открываем страницу 94
3. курим 3.9 War Story: String 'em Up
4. Завистливо смотрим на людей, который выиграли ультрабук и SSD диск.

Потому что:
-Это не та задача (да, она оперирует тем же алфавитом, но делает она другое)
-Она, конечно, использует не тот алгоритм
-Для строки в 65к символов (а это в 65000 раз меньше ограничений решаемой задачи) она работает 11 с лишним часов

Я так думаю, что тут нужно думать головой серьёзно больше, чем «да ну, можно скопипастить алгоритм из конспекта».
Конечно нужно. С другой стороны, знать про еще один существющий алгоритм, чтобы учесть его плюсы и минусы при разработке собственного, тоже нужно.
А есть ли пару реальных примеров тестовых данных? Ну, чтобы представлять, что придётся парсить.
Я неверно выразился. Имелось в виду не «хоть какие» данные, а реальные, больших объёмов, на которых можно было бы локально потестировать производительность алгоритмов.
Плюс вопрос в догонку — будет ли (и если да — то когда) автоматический бенчмарк вставлять в письма данные о времени выполнения задач. Т.е. смогу ли я оценить, что вот была версия №1, которая у вас там прошла тесты за 30 секунд, а версия №2 — за 25 секунда (и сделать выводы по поводу оптимальности алгоритмов).
Уточните пожалуйста соотношение размеров и количества ref и input данных.

В примере лежит Homo_sapiens.GRCh37.66.dna.chromosome.19.fa размером 60 Мб и две последовательности примерно по 2Кб.

То есть у нас есть одна большая ref строка и много (сколько примерно?) маленьких input последовательностей, важно то, что размер ref существенно больше чем размеры input. Правильно ли я все понял?
software.intel.com/ru-ru/articles/contest-accelerate-2012-problem/

Точное описание входных параметров
Ваше решение будет вызываться со следующими параметрами:
K — количество потоков, которые ваша программа может порождать, 1≤K≤40
M — минимальная длина подстрок, которые вам нужно найти, 6≤M≤2^32
ref — имя ref-файла, содержащего одну референсную строку (длина референсной строки менее 2^32 символов)
in — одно или несколько имен input-файлов, каждый из которых содержит одну или несколько input-строк. Число input-строк во всех файлах вместе — меньше, чем 2^32. Суммарная длина всех input-строк менее 2^32 символов.
Я не очень понял про Homo Sapiens. Если вы про пример в посте вверху, то это совпадение, я его брал почти из головы.

Вот ограничения на входные данные:
  • M — минимальная длина подстрок, которые вам нужно найти, 6≤M≤232
  • одна референсная строка длиной менее 232 символов
  • одна или несколько input-строк. Число input-строк — меньше, чем 232. Суммарная длина всех input-строк менее 232 символов
Ого! Интересно, 2 дня назад там этой строчки не было. Спрошу у коллег, спасибо.
Этак выходит, что 6≤M≤226, а референсы вообще уровня 211.
Интересный архивчик, словом :)
И того референсный код потребует 130 Гб ОЗУ :)
Ага, там в readme.txt (test_input_1.tar.bz2) написано:
>>In order to process big files, you need to be less greedy than our sample program.

Вообще можно ж хранить по 2 бита, а то и вообще строить что-то типа дерева словарного сжатия (Хаффман и т.п.). Участникам решать :)
Серьёзно упадет скорость доступа к данным. Одно дело — прямая адресация в массиве, другое дело — поиск под дереву или пара лишних битовых операции ради получения каждого элемента.
Но в принципе, конечно, выкрутиться можно :)
На форуме соревнования участниками показано, что код в примере НЕ решает задачу в поставленной формулировке. Есть целая куча примеров неоднозначного поведения — когда кода в примере трактует задачу по-одному, хотя её вполне можно понимать и по-другому (например, вопрос сдвига найденной последовательности вправо, вопрос вывода не всех найденных последовательностей — см. примеры «АААА» + «АААА» и «АСАС»+«АСАС»).

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

Информация

Дата основания
Местоположение
США
Сайт
www.intel.ru
Численность
5 001–10 000 человек
Дата регистрации
Представитель
Виктор Гурылев

Блог на Хабре