С наступившим! Нужны идеи и темы для небольших программ. Для наполнения портфолио. Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения? Может стоит посмотреть какие-нибудь open source-проекты?
Здравствуйте, Yagami, Вы писали:
Y>С наступившим! Нужны идеи и темы для небольших программ. Для наполнения портфолио. Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения? Может стоит посмотреть какие-нибудь open source-проекты?
Можешь отсюда взять. Если интересно поработать в области image processing -- обращайся, у меня есть несколько задачек до которых не доходят руки.
On 12.01.2013 8:27, Miroff wrote:
> Если интересно поработать в области image processing -- > обращайся, у меня есть несколько задачек до которых не доходят руки.
Гениально. Платить, как я понимаю не предполагается. Похоже,
действительно image&signal processing самые убогие области в бывшем СССР
— знаний и опыта требуется много, а платить никто не собирается. Как же
интересные задачи, зачем за них платить, чел и так себя эндорфинами
снабжает.
Y>Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения?
>> Если интересно поработать в области image processing -- >> обращайся, у меня есть несколько задачек до которых не доходят руки. V>Гениально. Платить, как я понимаю не предполагается. Похоже, V>действительно image&signal processing самые убогие области в бывшем СССР V>- знаний и опыта требуется много, а платить никто не собирается. Как же V>интересные задачи, зачем за них платить, чел и так себя эндорфинами V>снабжает.
Здравствуйте, Miroff, Вы писали:
M>Можешь отсюда взять. Если интересно поработать в области image processing -- обращайся, у меня есть несколько задачек до которых не доходят руки.
Интересно, какие бы вы предложили задачки по image processing?
Здравствуйте, Yagami, Вы писали:
Y>С наступившим! Нужны идеи и темы для небольших программ. Для наполнения портфолио. Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения? Может стоит посмотреть какие-нибудь open source-проекты?
Переведи внутренний парсер StyleCop на Roslyn. Работа технически простая, но объемная. Хотя за месяц реально все сделать. Туча людей скажет тебе спасибо, плюс получишь отличную строчку в резюме.
Здравствуйте, Yagami, Вы писали:
Y>С наступившим! Нужны идеи и темы для небольших программ. Для наполнения портфолио. Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения? Может стоит посмотреть какие-нибудь open source-проекты?
Здравствуйте, AndreyM16, Вы писали:
AM>Интересно, какие бы вы предложили задачки по image processing?
У меня есть набор out of copyright данных в виде сканов не поддающихся автоматическому OCR. Есть идея сделать что-то вроде рекаптчи, распознать сканы краудсорсингом и опубликовать.
Плюс есть классическая задача из machine vision. Сейчас появились дешевые качественные видеорегистраторы с GPS. Хочется сделать для OpenStreetMap инструмент, который позволит по записи регистратора определять дорожные знаки и разметку чтобы полуавтоматически добавлять их на карту.
Здравствуйте, Yagami, Вы писали:
Y>С наступившим! Нужны идеи и темы для небольших программ. Для наполнения портфолио. Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения? Может стоит посмотреть какие-нибудь open source-проекты?
Ради подобных целей и для развлечения пилю сейчас вот эту задачу (взято отсюда):
Допустим, у вас есть данные, которые представлены в виде
заголовка с фиксированным размером:
struct test {
unsigned char key[64];
uint64_t flags;
uint64_t crc;
uint64_t size;
};
где key — случайный набор байт, а size — случайная величина от 0 до 100 Мб.
Остальные параметры несущественны. У вас есть файл, в котором находится очень
много таких структур, причем после каждого такого заголовка идут $size байт с
данными (пусть это будут нули).
Т.е.:
[key0, flags, crc, size0][... $size0 bytes ...]
....
[keyN, flags, crc, sizeN][... $sizeN bytes ...]
Суммарный размер всех записей (размер файла с данными) — 20 Гб и больше.
Требуется отсортировать файл по ключам. Размер памяти ограничен 8Гб,
размер диска не ограничен. Напишите оптимизированное решение — то,
которое работает максимально быстро с учетом указанных системных ограничений.
Если делать не в лоб, есть много интересных моментов и простор для творчества.
Здравствуйте, ArtK, Вы писали:
AK>Если делать не в лоб, есть много интересных моментов и простор для творчества.
За один проход построить индекс (key, size, position), отсортировать индекс с помощью merge sort и пользуясь индексом один проход переупорядочить файл с данными это считается "в лоб"? Если да то интересны твои соображения как это еще оптимизировать.
Здравствуйте, Miroff, Вы писали:
M>Здравствуйте, ArtK, Вы писали:
AK>>Если делать не в лоб, есть много интересных моментов и простор для творчества.
M>За один проход построить индекс (key, size, position), отсортировать индекс с помощью merge sort и пользуясь индексом один проход переупорядочить файл с данными это считается "в лоб"? Если да то интересны твои соображения как это еще оптимизировать.
Записи в файле имеют не фиксированный размер. Сначало нужно прочитать заголовок, потом уже сами данные. Если читать sizeof(test) байт, затем seek-ать данные, получатся долго, можно как минимум в два раза быстрее.
Как сериализовать и десериализовать структуру, чтобы небыло проблем с мусором при выравнивании памяти?
Как отсортировать индекс, если он не помещается в памяти?
Merge sort требует дополнительный буфер, к тому же работает медленней, чем quick sort. Можно конечно сделать in place merge sort, но зачем если всё равно будет медленней чем quick sort?
Можно попробовать потюнить radix sort, и он будет работать ещё быстрее чем quick sort.
Здравствуйте, ArtK, Вы писали:
AK>Записи в файле имеют не фиксированный размер. Сначало нужно прочитать заголовок, потом уже сами данные. Если читать sizeof(test) байт, затем seek-ать данные, получатся долго, можно как минимум в два раза быстрее.
Читаем заголовок фиксированного размера, опеределяем key и size, пропускаем следующие size байт. Можно попытаться читать блоками в размер кластера, но на практике это не оказывает влияния благодаря файловым буферам ОС.
AK>Как сериализовать и десериализовать структуру, чтобы небыло проблем с мусором при выравнивании памяти?
Это овердизайн. Записи в индексе короткие и фиксированной длины. На фоне тяжелой работы с диском оверхед на выравнивание памяти будет незаметен.
AK>Как отсортировать индекс, если он не помещается в памяти?
Читаем блок который влезает, сортируем quick sort'ом, пишем на диск. Так для всех блоков. Затем merge sort'ом сливаем блоки за один проход.
AK>Merge sort требует дополнительный буфер, к тому же работает медленней, чем quick sort. Можно конечно сделать in place merge sort, но зачем если всё равно будет медленней чем quick sort?
Быстрая сортировка сосет если данные не влезают в память.
AK>Можно попробовать потюнить radix sort, и он будет работать ещё быстрее чем quick sort.
Radix sort хорош для собеседований. На практике он пригоден чуть более чем нигде.
Дай как я угадаю, интересные моменты возникают у тебя оттого что ты пытаешься сортировать файл in place какой-то вариацией быстрой сортировки?
Здравствуйте, Miroff, Вы писали:
M>Здравствуйте, ArtK, Вы писали:
AK>>Записи в файле имеют не фиксированный размер. Сначало нужно прочитать заголовок, потом уже сами данные. Если читать sizeof(test) байт, затем seek-ать данные, получатся долго, можно как минимум в два раза быстрее.
M>Читаем заголовок фиксированного размера, опеределяем key и size, пропускаем следующие size байт. Можно попытаться читать блоками в размер кластера, но на практике это не оказывает влияния благодаря файловым буферам ОС.
Если читать блоками, нужно очень аккуратно обрабатывать границы блоков, т.к. эта граница может оказаться на середине заголовка.
AK>>Как сериализовать и десериализовать структуру, чтобы небыло проблем с мусором при выравнивании памяти?
M>Это овердизайн. Записи в индексе короткие и фиксированной длины. На фоне тяжелой работы с диском оверхед на выравнивание памяти будет незаметен.
Проблема не в оверхеде чтения, а в кроссплатформенной сериализации.
AK>>Как отсортировать индекс, если он не помещается в памяти?
M>Читаем блок который влезает, сортируем quick sort'ом, пишем на диск. Так для всех блоков. Затем merge sort'ом сливаем блоки за один проход.
Зачем сливать merge sort-ом, когда можно просто использовать merge отсортированных блоков?
AK>>Merge sort требует дополнительный буфер, к тому же работает медленней, чем quick sort. Можно конечно сделать in place merge sort, но зачем если всё равно будет медленней чем quick sort?
M>Быстрая сортировка сосет если данные не влезают в память.
Ну это кагбе понятно
AK>>Можно попробовать потюнить radix sort, и он будет работать ещё быстрее чем quick sort.
M>Radix sort хорош для собеседований. На практике он пригоден чуть более чем нигде.
Можешь привести пример, когда радикс справляется хуже быстрой сортировки?
M>Дай как я угадаю, интересные моменты возникают у тебя оттого что ты пытаешься сортировать файл in place какой-то вариацией быстрой сортировки?
>> Это везде так. V>То-бишь опердни рулят, а всякое распознавание образов и т.п. идет лесом?
Прикинь.
Распознавание на приемлемом уровне уже написано, а улучшать бизнесу смысла особого нет.
Как прижмёт — начнут думать.
А опердни нужны еще вчера.
On 25.01.2013 14:27, dr. Acula wrote:
> Прикинь. > Распознавание на приемлемом уровне уже написано, а улучшать бизнесу > смысла особого нет. > Как прижмёт — начнут думать. > А опердни нужны еще вчера.
Ну да, об этом и пишу.
Здравствуйте, ArtK, Вы писали:
AK>Если делать не в лоб, есть много интересных моментов и простор для творчества.
Там есть несколько интересных техник. Но все техники работают в одинх условиях и не работают в других. Т.е. какие-то константы нужно подгонять уже на актуальной машине, с учетом ее производительности.
Теперь несколько соображений. Преамбула. Очевидно, что в какой-то момент будет внешняя сортировка (или даже с самого начала, но это вряд ли). Я бы тоже делил на отсортированные блоки и мержил их.
1. Для "маленьких" блоков вместо "ссылки" на блок в исходном файле нужно хранить сам блок. Потому что диск обсикается ходить за мелочью, если она плохо распределена в исходном файле и файл в основном состоит из маленьких записей. Файлы же при merge читаются вполне последовательно и достаточно крупными блоками. Точное определение "маленького" зависит от характеристик исходной системы.
2. "Большие" блоки перед внешней сотрировкой я бы в большинстве случаев хранил в файлах, которые на последнем этапе объединяются. Соображения те же, что и в предыдущем пункте — не нужны лишние адресации на диске. Но здесь уже все зависит от количества индексных файлов. Если вдруг у нас на последнем этапе будет много файлов, то все будет сложнее. Выполнять слияние 100 файлов в один проход — не очень хорошая идея (если они все из больших записей). Т.е. на самом деле последний merge может быть в несколько этапов. Уже на паре сотен тысяч индексов в память из индекса можно положить не так много и может иметь смысл заменть много "случайных" чтений на большее количество относительно последовательных. В принципе, там даже при таких размерах индексов исходные файлы еще не запредельные.
3. Вероятно, стоит использовать многопоточность и для in-memory sorting читать данные в одном потоке, а сортировать — в другом. Или асинхронный ввод/вывод использовать. Все равно задача i/o bound. Но это уменьшит объем памяти для одной итерации в два раза. Потоков больше двух не нужно в любом случае.
4. На фоне предыдущего шага уже не важно (особенно при многопоточности) но можно еще поизвращаться. Стоит посмотреть, не стоит ли и в памяти вместо "чистого индекса" хранить "маленькие" записи в самом индексе. Здесь понятие "маленький" будет совершенно не такое, как в первом пункте. Разница — на записи (либо последовательные области памяти, либо seek в памяти).
5. Может быть, для in-memory сортировки должны использоваться разные подходы. Где-то до размера <cpu-cache>/2-<cpu-cache> — быстрая сортировка. А затем эти блоки можно мержить. Слияние даст последовательные доступы к блокам данных, что вполне может аппаратно запрефетчится на чтение и быть быстрее, чем промахи при "чистой" быстрой сортировке. Очевидно, замерять разницу нужно на железе.
Из того, что выше, актуальны пп. 1-3. 4-5 — опциональны. Я бы взял второй подход (читаем фрагмент файла, записываем в отсортированном виде весь фрагмент в файл (в памяти — быстрая сортировка индекса, скорее всего)) и в конце слияем эти файлы. Проблемы масштабируемости лечатся добавлением памяти на сервер. Можно даже и выделенный сервер собрать. Это может даже дешевле отказаться, чем сложное оптимизированное решение в коде (в котором возможны еще и ошибки, т.е. кроме реализации добавляется и стоимость поддержки).
Здравствуйте, Yagami, Вы писали:
Y>С наступившим! Нужны идеи и темы для небольших программ. Для наполнения портфолио. Чтобы было не стыдно показать работодателю. Интересуют: С++, Python и различные разделы математики (матан, дискретка, теор.вер. и т.д). Какие будут предложения? Может стоит посмотреть какие-нибудь open source-проекты?
