Всем привет. Нашел, наконец-то, красивое решение задачи о поиске 2-ух недублирующихся элементов в большом входном потоке целых чисел (см. концовку моего предыдущего поста). Своим умом, к сожалению, до этого решения не дошел, но так как решение очень красивое, и мне оно понравилось, привожу его ниже (кстати, еще раз убедился во вменяемости практически абсолютного большинства участников форума rsdn.ru :).
Итак, напомню условие задачи. Есть большой входной поток целых чисел, про который известно, что в нем все числа дублируются кроме двух. Найти эти 2 числа за константное количество проходов с использованием константного количества памяти.
вторник, 14 сентября 2010 г.
четверг, 2 сентября 2010 г.
Задача о поиске недублирующихся элементов в потоке
Недавно столкнулся с еще одной интересной задачей. Звучит она так: имеется входной поток целых чисел. Известно, что в нем все элементы дублируются, кроме одного. Найти этот один элемент за константное количество проходов (O(1)) , используя константное же количество памяти.
Первоначально пришла в голову идея использовать какой-то хэш-массив, в котором ключами будут значения элементов входного потока, а значениями - число вхождений того или иного элемента в поток. Сложность в том, что заранее неизвестно, в каком диапазоне числа входного потока. Если предположить, что размер int'а 32 бита, то в хэше возможно 2^32 элементов, что, в общем, достаточно круто )
Но затем неожиданно меня посетила неплохая идея: а что, если воспользоваться операцией XOR, для которой характерны следующие правила: A XOR A = 0 и 0 XOR A = A.
Тогда просто проксорив все элементы входного потока, мы получим на выходе значение недублирующегося элемента, ибо
A XOR B XOR A XOR C XOR B = C
То есть, для решения задачи нужен всего 1 проход по всем элементам и одна переменная, аккумулирующая результат, что, согласитесь, неплохо.
А теперь внимание. Как можно решить задачу, если в потоке не один недублирующийся элемента, а два ? Мне пока что-то ничего в голову не приходит.
Первоначально пришла в голову идея использовать какой-то хэш-массив, в котором ключами будут значения элементов входного потока, а значениями - число вхождений того или иного элемента в поток. Сложность в том, что заранее неизвестно, в каком диапазоне числа входного потока. Если предположить, что размер int'а 32 бита, то в хэше возможно 2^32 элементов, что, в общем, достаточно круто )
Но затем неожиданно меня посетила неплохая идея: а что, если воспользоваться операцией XOR, для которой характерны следующие правила: A XOR A = 0 и 0 XOR A = A.
Тогда просто проксорив все элементы входного потока, мы получим на выходе значение недублирующегося элемента, ибо
A XOR B XOR A XOR C XOR B = C
То есть, для решения задачи нужен всего 1 проход по всем элементам и одна переменная, аккумулирующая результат, что, согласитесь, неплохо.
А теперь внимание. Как можно решить задачу, если в потоке не один недублирующийся элемента, а два ? Мне пока что-то ничего в голову не приходит.
вторник, 10 августа 2010 г.
Почему нас так не любят за рубежом ? )
Лазил на днях по гуглю и нашел сервис Omegle, предоставляющий возможность пообщаться tet-a-tet с каким-нибудь случайным человеком (есть мнение, что таких сервисов достаточно много, но речь сейчас не об этом). Сервис забугорный, поэтому общение предполагает быть на инглише.
Май инглиш из вэри бэд, но всё равно попробовал ради шутки посмотреть, что получится. Ниже привожу логи 2-ух моих непродолжительных бесед с 2-мя разными представителями дальнего, как я понимаю, зарубежья.
Май инглиш из вэри бэд, но всё равно попробовал ради шутки посмотреть, что получится. Ниже привожу логи 2-ух моих непродолжительных бесед с 2-мя разными представителями дальнего, как я понимаю, зарубежья.
четверг, 29 июля 2010 г.
Задача о картине, веревке и гвоздях
Недавно с помощью знакомого откопал, как я понимаю, старую задачу, условие которой формулируется следующим образом: Имеется картина, к которой обоими концами прикреплена длинная веревка. Необходимо повесить её на стене с помощью N гвоздей таким образом, чтобы при удалении любого (одного) гвоздя картина и веревка падали.
Для случая, когда гвоздь всего один, задача решается элементарно.
Будем разбираться, как её решить для 2-ух и более гвоздей. Рассмотрим ситуацию с 2-мя гвоздями. Обозначим их A и B. Введем операции (+) и (-), когда веревка обматывает гвоздь по часовой и, соответственно, против часовой стрелки. Таким образом, A + B означает, что гвозди A и B обмотаны веревкой по часовой стрелке 1 раз (по отдельности или вместе - в данном случае это не играет особой роли).
Также понятно, что A + (-A) = 0, так как мы оборачиваем гвоздь А по часовой стрелке, и тут же снимаем с него веревку против часовой стрелки. Итоговое значение 0 означает, что картину с веревкой ничего не удерживает, и они гарантированно упадут.
Удаление гвоздя будем отмечать заменой соответствующей буквы на число 0 (гвоздь перестает играть роль в процессе удержания картины). Таким образом, для того, чтобы условие задачи выполнялось, необходимо получить такую формулу, когда замена какой-либо одной (любой) буквы, обозначающей гвоздь, приводит всю формулу к нулевому значению.
Для случая, когда гвоздь всего один, задача решается элементарно.
Будем разбираться, как её решить для 2-ух и более гвоздей. Рассмотрим ситуацию с 2-мя гвоздями. Обозначим их A и B. Введем операции (+) и (-), когда веревка обматывает гвоздь по часовой и, соответственно, против часовой стрелки. Таким образом, A + B означает, что гвозди A и B обмотаны веревкой по часовой стрелке 1 раз (по отдельности или вместе - в данном случае это не играет особой роли).
Также понятно, что A + (-A) = 0, так как мы оборачиваем гвоздь А по часовой стрелке, и тут же снимаем с него веревку против часовой стрелки. Итоговое значение 0 означает, что картину с веревкой ничего не удерживает, и они гарантированно упадут.
Удаление гвоздя будем отмечать заменой соответствующей буквы на число 0 (гвоздь перестает играть роль в процессе удержания картины). Таким образом, для того, чтобы условие задачи выполнялось, необходимо получить такую формулу, когда замена какой-либо одной (любой) буквы, обозначающей гвоздь, приводит всю формулу к нулевому значению.
суббота, 24 июля 2010 г.
Фильм "Рядовой Александр Матросов"
Сегодня посмотрел старый советский фильм "Рядовой Александр Матросов", снятый в 1947 году. Ну что сказать... Конечно, сейчас этот фильм выглядит немного наивным, и та сюжетная линия, по которой он построен, полностью совпадает с историей жизни Александра Матросова, широко известной в советское время. Это уже после развала СССР
начались какие-то подвижки в сторону открытия ранее неизвестных фактов из его биографии (оказывается, что и настоящее имя героя не Александр Матросов, и родился он совсем не в Днепропетровске, и подробности самого подвига весьма туманны).
Но с другой стороны - а так ли это важно на самом деле ? Главное - человек отдал самое дорогое, что у него есть - жизнь - за свободу Родины, за то, чтобы мы с вами могли сегодня жить...
Так что поклонимся героям Великой Отечественной войны. Всем - и тем, имена которых известны, и тем, чьи останки до сих пор лежат не найденными в земле.
Вечная Слава героям.
начались какие-то подвижки в сторону открытия ранее неизвестных фактов из его биографии (оказывается, что и настоящее имя героя не Александр Матросов, и родился он совсем не в Днепропетровске, и подробности самого подвига весьма туманны).
Но с другой стороны - а так ли это важно на самом деле ? Главное - человек отдал самое дорогое, что у него есть - жизнь - за свободу Родины, за то, чтобы мы с вами могли сегодня жить...
Так что поклонимся героям Великой Отечественной войны. Всем - и тем, имена которых известны, и тем, чьи останки до сих пор лежат не найденными в земле.
Вечная Слава героям.
пятница, 23 июля 2010 г.
Утилита для очистки ключевых слов KCleaner
На днях написал на C++ небольшую утилиту KCleaner (от Keys Cleaner) в помощь веб-мастерам и SEO-шникам. Она позволяет чистить базы кеев по спискам стоп-слов. Утилита консольная, работает в среде OS Windows (гарантированно проверял работу в Windows XP SP2).
Главный упор при её написании я делал на возможность обработки больших массивов данных с сохранением высокой скорости работы. Так, например, для обработки базы ключевиков объемом ~500 000 ключевых слов при файле стоп-слов объемом ~50 000 слов моей утилите требуется около 7-8 секунд на железе Sempron 2500 1.4GHz + 512MB RAM.
понедельник, 19 июля 2010 г.
Рассказ Густава Майринка "Звон в ушах"
Сегодня случайно в одном из ЖЖ-комментариев Ильи Прутова наткнулся на короткий рассказ Густава Майринка "Звон в ушах". Про Майринка, к сожалению, до сего дня практически ничего не знал, хотя фамилию писателя раньше уже слышал. Рассказ (написанный им, как оказалось, еще в 1903 году!) просто чудовищен по красоте. Очень здорово передана мрачная, угнетающая атмосфера, а последняя фраза ("Кто заткнет уши, может услышать, как звенит он внутри"), которая как бы повисает в воздухе, служит замечательным финальным аккордом.
Еще раз убедился, что даже в небольшом по размеру литературном произведении можно передать очень много всего. А этот рассказ, на мой взгляд, стоит иных многостраничных романов и повестей. В общем, рекомендую к прочтению. Ну и, так как размер рассказа очень мал, привожу ниже целиком этот сгусток мастерства Автора:
Еще раз убедился, что даже в небольшом по размеру литературном произведении можно передать очень много всего. А этот рассказ, на мой взгляд, стоит иных многостраничных романов и повестей. В общем, рекомендую к прочтению. Ну и, так как размер рассказа очень мал, привожу ниже целиком этот сгусток мастерства Автора:
Подписаться на:
Сообщения (Atom)