Открыть список
Как стать автором
Обновить
9
Карма
0
Рейтинг

Пользователь

Поиск часто встречающихся элементов в массиве

Высокая производительностьData MiningАлгоритмы
Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.
Читать дальше →
Всего голосов 105: ↑98 и ↓7 +91
Просмотры103K
Комментарии 38

Сражение при Asakai: как EVE Online справляется с гигантскими битвами

Блог компании Apps4AllРазработка игр
Перевод
Битва у Asakai стала второй по количеству столкнувшихся кораблей в истории EVE Online (об этом прекрасно написал комрад madmaxcorp, там же вы можете посмотреть без преувеличения галактической красоты видео очевидца). История сражения интересна сама по себе (человеческая ошибка), но нас традиционно больше интересует что же было с серверами игры во время этой сумасшедшей битвы, как CCP (создатель EVE Online) удается справляться с такими нагрузками?

«Наша команда поддержки (игровые мастера, GMs) следит за гигантскими битвами, подобными этим», — говорит один из разработчиков. «У нас есть веб-страница со статусом кластера, на которой появляются большие красные цифры в случае перегрузки нод в сражениях. Так что довольно легко видеть что происходит». Более интересно то, что стоит за этими цифрами.

Читать дальше →
Всего голосов 137: ↑129 и ↓8 +121
Просмотры102.1K
Комментарии 166

Альтернатива Dropbox от BitTorrent

Децентрализованные сети

BitTorrent Inc. анонсировало новое приложение позволяющее пользователям синхронизировать папки посредством bittorent протокола с шифрованием. Программа бесплатна, не имеет ограничений на объемы хранилища и может использоваться как резервное хранилище или общая папка. BitTorrent Sync будет особенно полезна для тех групп пользователей, которым необходимо обмениваться через интернет большими файлами.
Читать дальше →
Всего голосов 102: ↑93 и ↓9 +84
Просмотры73.3K
Комментарии 150

Исключительная красота исходного кода Doom 3

ПрограммированиеC++Разработка игр
Перевод
Recovery mode
image

Сегодня вас ждет рассказ об исходном коде Doom 3 и о том, насколько он красив.
Да, красив. Позвольте мне объясниться.
Читать дальше →
Всего голосов 281: ↑256 и ↓25 +231
Просмотры213.5K
Комментарии 245

Просмотр изображений OpenCV во время отладки C++ кода в Visual Studio

C++Visual StudioОбработка изображений
Из песочницы


Если вы пишете код для обработки изображений на С++, вы наверняка используете замечательную библиотеку OpenCV. Уверен, вам не раз хотелось посмотреть на изображения в процессе отладки вашего кода. Для этого можно использовать такие удобные функции как imshow или imwrite. Однако это требует модификации исходного кода, а любая современная IDE во время отладки позволяет смотреть значения переменных на лету. Вот было бы здорово так же смотреть изображения?

Если в качестве IDE вы пользуетесь Visual Studio, то знаете, что с .NET в этом плане всё проще. Однако речь идёт про OpenCV, а это только native C++, только хардкор. В этой статье я расскажу, как всё-таки заставить Visual Studio показывать изображения прямо в процессе отладки и дам ссылку на готовое решение. А также коротко расскажу о способах кастомизации Visual Studio.
Читать дальше →
Всего голосов 52: ↑49 и ↓3 +46
Просмотры17.8K
Комментарии 6

Дерево Фенвика

Алгоритмы
Из песочницы
Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

Что это?


Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
• позволяет изменять значение любого элемента за O(log N);
• требует памяти O(N);
Читать дальше →
Всего голосов 81: ↑73 и ↓8 +65
Просмотры41.6K
Комментарии 37

Обзор e-Learning трекеров или Век живи — век учись!

Децентрализованные сети
Все чаще можно услышать про универсальных трекеров-монстров типа ThePirateBay.org, torrents.ru или упоминания трекеров музыкальной либо игровой тематики. Но помимо них давно существуют торрент-трекеры обучающей направленности, о которых мало что известно рядовому пользователю. В основном, это закрытые сообщества образованных людей с регистрацией по приглашениям, которые обмениваются обучающими материалами, будь-то электронные книги, обучающее видео, CBT (computer based trainings), аудио-книги, презентации с конференций или софт для обучения. Преобладающая часть материалов связана с ИТ-технологиями и поэтому будет особенно полезна ИТ-специалистам, от студента, изучающего Linux, PHP или C# и до гуру, который готовится к сдаче CCIE. Также присутствует материал, посвященный изучению иностранных языков, психологии, саморазвитию, соблазнению, развитию бизнес-навыков. Если ты подумываешь сдать на CCNA, MCSE, RHCE, CISSP, Network+, PMP, IELTS/TOEFL и так далее — то здесь можно найти все необходимое и даже больше. Под катом находится обзор англоязычных ресурсов обучающей направленности.
Поехали!
Всего голосов 74: ↑73 и ↓1 +72
Просмотры23.5K
Комментарии 224

Фотографируем через WIA на .NET

.NET
imageЗадача поста — освежить информацию о работе с WIA в .NET, лежащую на просторах сети, т.к. большинство примеров безбожно устарели (они не работают), поделиться опытом с интересующимися и спросить совета у бывалых. Я думаю, совместно обсудить некоторые моменты, будет полезно для коллег, занимающихся подобными задачами. Постараюсь разжевать все моменты.

Мотив был таков: в программе, где хранится информация о людях есть их фотографии, но фотографии туда попадают сложным путем. Берем бумажный оригинал фото (их приносят люди вместе с документами), сканируем в файл, открываем в простом редакторе, кадрируем под 3х4см, сохраняем, в программе открываем анкету человека и там уже добавляем ему фото из готового файла.

Сейчас в программе несколько тысяч человек и стоит задача всех их сфотографировать красиво, потому что они приносят фотографии просто ужасного качества и с разным процентом заполнения лица. Дело за малым: повесить экран, выставить свет, стул, штатив, камера, USB… и наша программа.
Под катом простой пример и рассуждения
Всего голосов 26: ↑25 и ↓1 +24
Просмотры17.9K
Комментарии 21

Литдетектив: «дождливые» идиомы в английском

Блог компании ABBYY
Tutorial
Из всех английских идиом именно «дождливые» кажутся русскому человеку полной бессмыслицей: тяжело понять на первый взгляд, отчего «у них» во время ливня с неба падают животные разной степени экзотичности и опасные для жизни предметы. It’s raining cats and dogs, it rains pitchforks and stair-rods – происхождение этих фраз туманно, как сам Альбион. И у каждой, как у достойного английского анекдота, своя изюминка.

Начнём с самого тяжёлого случая – с «cats and dogs». Британские учёные этимологи до сих пор не уверены, что это такое – удачный словесный пируэт XVIII века, описание глобального природного катаклизма или же попытка отразить в шуточно-лаконичной форме завывания бунтующей стихии.

Читать дальше →
Всего голосов 112: ↑96 и ↓16 +80
Просмотры58.4K
Комментарии 56

Введение в модулярную арифметику

Алгоритмы
В обычной жизни мы обычно пользуемся позиционной системой счисления. В позиционной системе счисления значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда) [1]. Однако существуют и так называемые «непозиционные системы счисления», к одной из которых относится «система остаточных классов» (СОК) (или в оригинале Residue Number System (RNS)), являющаяся основой модулярной арифметики. Модулярная арифметика базируется на «Китайской теореме об остатках» [2], которая для нашего случая звучит следующим образом:
Для любой системы взаимно простых чисел p1, … pn, любое число X из диапазона [0; M), где M = p1*p2*…*pn взаимооднозначно представимо в виде вектора (a1, a2, …, an), где ai = X%pi (здесь и далее «%» — операция взятия остатка от целочисленного деления X на pi).
p1, … pn – модули системы
a1, a2, …, an – остатки (вычеты) числа по заданной системе модулей

Читать дальше →
Всего голосов 85: ↑80 и ↓5 +75
Просмотры52.7K
Комментарии 37

Информация

В рейтинге
3,872-й
Зарегистрирован
Активность