Просмотр сообщений

В этом разделе можно просмотреть все сообщения, сделанные этим пользователем.


Темы - Губанов Сергей Юрьевич

Страницы: 1 [2] 3
16
Общий раздел / Смёржить отрезки
« : Октябрь 23, 2012, 01:47:07 pm »
На целочисленной (типа UInt64) прямой задан список отрезков {{начало1, конец1}, {начало2, конец2}, {начало3, конец3},...}. Отрезки могут соприкасаться, пересекаться и даже целиком поглощаться друг другом. Надо написать программу, которая быстро-быстро смёржит все пересечения/соприкосновения/поглощения и выдаст нормальный список отрезков (без пересечений/соприкосновений/поглощений).

Вопрос: как сделать это эффективно?

P. S.
Это списки диапазонов телефонных номеров. Всего номеров будет что-то около миллиона, списки конечно покороче. Не знаю точно, может быть 100 отрезков в списке, а может быть и 1000.

17
Общий раздел / БД через расшаренную память
« : Октябрь 10, 2012, 04:37:54 am »
Мучает меня дурацкая идея...

Есть данные. В основном данные нужны в режиме только для чтения. Изменяются они редко. Данных может быть много - гигабайты.

Есть программа. Программа стартует, медленно всасывает в себя все данные, а потом очень быстро работает.

Программ может быть несколько (у меня их уже две). Запускаются они на одном большом сервере.

Вроде всё нормально, однако:
1) Жалко память (копий данных столько сколько программ).
2) Жалко при старте тратить время на всасывание данных (хочется иметь возможность очень быстрого рестарта).

Дурацкая идея:
Сделать "сервер" данных, который будет шарить свою память. Он (ре)стартует медленно.
Остальные программы при старте будут всего лишь маппить память. Выгоды: мгновенный рестарт, данные не копируются.

Сколько же тут подводных камней...

18
Максимальное количество потоков = (размер виртуальной памяти включая файл подкачки) / (размер виртуальной памяти резервируемой под стек потока).

Под Windows 7 минимальный размер памяти резервируемый под стек потока 256 Кб.

Создал я файл подкачки в 200 000 Мб и посмотрел что будет:

19
Общий раздел / 400 лет народному ополчению
« : Сентябрь 06, 2012, 03:15:03 pm »
400 лет назад народ отвоевал Москву у поляков...

Последние несколько лет некоторыми товарищами продвигался мем: "народные ополченцы" -- это такие ламеры от программирования. Особо не задумываясь я и сам иногда ругался "народными ополченцами". До меня только недавно дошло на сколько же этот мем русофобский.

Народное ополчение - святое, ламеры от программирования - позор. Мысль связать одно с другим ужасна.

20
Статья на хабре:

Куда стоило бы развиваться Delphi вместо того, куда оно развивается сейчас
http://habrahabr.ru/post/150943/

> А вот про возможность использовать в native Delphi мощь библиотек .net я вовсе не слыхал.

Посмеялся. А использования классов Java в нативном коде он не хочет?  :)  :)  :)

По моему у Борланда после седьмой дельфи было два альтернативных пути:
1) делать свою собственную платформу навроде дотнета, явы или блэкбокса;
2) до последнего солдата выдавливать С++ из его ниш.

Борланд сглупила и легла под дотнет, тем самым утратила, так сказать, суверенитет со всеми вытекающими последствиями.

21
Общий раздел / Велосипедная СУБД
« : Август 28, 2012, 01:57:31 pm »
Однажды понадобилось иметь персистентную коллекцию неких записей. В процессе работы программы записи могут изменяться, удаляться, добавляться. Держать для неё отдельную СУБД - это как из пушки по воробъям, так что просто завёл файл. Встал вопрос как организовать с ним работу. Я выделил три условия:

1) С одной стороны размер этого файла не очень гигантский в том смысле, что при старте программа зачитывает его целиком в оперативку. Пусть программа стартует медленно, зато работает быстро.

2) С другой стороны его размер достаточно велик для того чтобы при изменении одной или нескольких записей перезаписывать файл целиком сбрасывая все записи из оперативки на диск. Жесткий диск может интенсивно использоваться другими программами работающими на этом же компьютере, поэтому полная перезапись файла может занять несколько секунд.

3) Если во время записи в файл произойдёт авария (выключение питания, падение программы), то данные не должны серьёзно испортиться. При рестарте программа перечитывая файл должна сама исправить ошибки в файле.

Хотелось бы узнать кто как поступил бы в этой ситуации.

Я организовал работу с этим файлом так.
Каждая запись снабжается уникальным идентификатором. Данные в файле представляют собой набор команд двух типов:
1) добавить или перезаписать запись с таким-то идентификатором такими-то значениями,
2) удалить запись с таким-то идентификатором.
Программа стартует, читает файл и выполняет команды; после выполнения всех команд в оперативной памяти получается итоговый набор записей. Когда в процессе работы программы какая-то запись удаляется, то в конец того файла дописывается команда "удалить запись с таким-то идентификатором". Когда какая-то запись добавляется или изменяется, то в конец файла дописывается команда "добавить или перезаписать запись с таким-то идентификатором такими-то значениями". То есть во время работы программы в файл дописываются только изменения -- это очень быстро (правда занимает больше места на диске). Важно что запись всегда идёт только в конец файла. Если во время записи данных в файл произойдёт авария, то при рестарте программа дочитав до этого места обнаружит ошибку в формате данных и перезапишет файл автоматически удалив эту ошибку. Ошибка может быть только в конце файла! Если при старте программа прочитав файл обнаруживает, что количество команд в нём более чем в два раза превышает итоговое количество записей, то она перезапишет файл (тем самым уменьшит его размер более чем в 2 раза). Перезапись осуществляется естественно сначала во временный файл, а затем выполняется (как бы атомарная) замена старого файла новым.

22
Общий раздел / Премия Юрия Мильнера
« : Июль 31, 2012, 09:15:20 pm »
http://vz.ru/news/2012/7/31/591205.html

Цитировать
Фонд основателя Mail.ru учредил премию в области фундаментальной физики

31 июля 2012, 20:56

Благотворительный фонд бизнесмена Юрия Мильнера, сооснователя Mail.ru и совладельца фонда DST, создал ежегодную премию за крупные достижения в области фундаментальной физики.

Согласно сообщению фонда, премии будут вручаться в двух категориях – «Фундаментальная физика» с размером премии в 3 млн долларов и «Новые горизонты физики» с премией в 100 тыс. долларов, передает «Интерфакс».

Размер этой премии более чем в два раза превышает Нобелевскую премию, лауреаты которой с 2001 года получают по 10 млн шведских крон (в 2011 году в пересчете на доллары США - 1,4 млн долларов).

Согласно сообщению, лауреатами премии Мильнера в категории «Фундаментальная физика» уже стали девять ученых, получивших совокупно 27 млн долларов.

Все лауреаты премии войдут в состав отборочной комиссии, которая будет в дальнейшем принимать решения о присуждении новых премий. Все будущие лауреаты премий также получат приглашения войти в состав отборочной комиссии.

Условия премии предполагают, что она будет ежегодно вручаться за значительные достижения как в области фундаментальной физики, так и в областях, тесно с ней связанных. У премии нет возрастных ограничений, денежное вознаграждение может быть поделено между любым количеством ученых.

Сам Мильнер закончил МГУ с дипломом в области теоретической физики и после окончания университета работал в Физическом институте РАН.

Предприниматель построил успешный бизнес в IT-сфере. В частности, он стал одним из основателей Mail.ru Group, совместно с Алишером Усмановым и партнерами создал фонд DST, инвестировавший в Facebook на раннем этапе развития компании.

23
Общий раздел / Цена dynamic в C# 2010 .Net 4.0
« : Июнь 20, 2012, 01:14:51 pm »
Добавила Микрософт в C# 2010 ключевое слово dynamic для поддержки программирования в стиле динамических языков а-ля Питон. Динамика реализуется через reflection. Дошли руки померить скорость работы.

Будем вызывать процедуру Foo класса MyObject:
public sealed class MyObject
{
   public static int sum;

   public void Foo (int x, int y, int z)
   {
      sum = sum + x + y + z;
   }
}

Обычный статический вызов:
public static void Test0 (MyObject x)
{
   x.Foo(1, 2, 3);
}

Обычный вызов с предварительным динамическим приведением типа:
public static void Test1 (object x)
{
   ((MyObject)x).Foo(1, 2, 3);
}

Чисто динамический вызов (а-ля Питон):
public static void Test2 (dynamic x)
{
   x.Foo(1, 2, 3);
}

Время затраченное на миллиард вызовов:
Test0   1.90 секунд
Test1   1.95 секунд
Test2  24.37 секунд

24
Общий раздел / ЕГЭ
« : Июнь 18, 2012, 09:16:46 pm »
А как это так получилось, что из 800'000 школьников сдававших ЕГЭ по математике на пятёрку (то есть на 100 баллов) её сдали всего 51 человек? Не пятьдесят одна тысяча, а просто пятьдесят один??? Школьную-то математику???

Мне на ум приходят всего два варианта (возможна их смесь):

1) Заданий было реально очень много, а времени дали мало, чисто физически решить все задания абсолютно никто не успел, а те 51 человек тупо "списали" заранее им известные ответы.

2) Одно или несколько заданий преднамеренно или непреднамеренно имели "правильными" математически неверные ответы. Отвечая на них математически верно, школьники тем самым отвечали "не правильно", а 51 человек тупо "списали" заранее им известные "правильные" ответы.

Вариант, что из 800'000 и в самом деле есть всего 51 отличник я отметаю как абсолютно безумный поскольку речь идёт об обычной простяцкой школьной математике.

 :o :o :o

25
Общий раздел / Новости IT
« : Июнь 15, 2012, 09:31:34 am »
У GPU и CPU гибридного процессора AMD Kaveri будет общее адресное пространство памяти

http://www.ixbt.com/news/hard/index.shtml?15/91/61

Примерно одновременно с APU Kaveri выйдут процессоры Intel Haswell, у которых, при всех достоинствах, не будет единого адресного пространства для x86-совместимых ядер и интегрированной графики.

26
Применил технику оптимизации из A6 для ускорения обычного линейного поиска.

Ускорилось на 11%.

Эталонный алгоритм:
static long L1 (char* begin)
{
   char* p = begin;
   while (*p != 0)
   {
      p++;
   }
   return (long)(p - begin);
}

Ускоренный алгоритм:
static long L2 (char* begin)
{
   char* p = begin;
   while (*p != 0)
   {
      if (*(p + 1) == 0)
      {
         p++;
      }
      else if (*(p + 2) == 0)
      {
         p += 2;
      }
      else
      {
         p += 3;
      }
   }
   return (long)(p - begin);
}

Прогнал сто раз по массиву из миллиарда букв:
L1  27.9264553 секунд
L2  24.9913335 секунд

Добавление более двух веток if-else результата не изменило. Использование всего одной ветки if-else результат только ухудшило.

Для маленьких массивов целиком убирающихся в кэш процессора ускорение составило всего 1%.

Win 7 64bit, .Net 4.0, i7 3770K.

27
Речь о численном решении всяческих волновых уравнений с сильно локализованными волновыми пакетами. Хочется пространственную сетку сделать неравномерной, так чтобы в области нахождения волнового пакета количество точек было очень большим, а в остальной части (пустого) пространства -- малым. И ещё подвижной, чтобы по мере распространения волнового пакета плотность точек решётки под него подстраивалась.

Кто нибудь слышал про подобное?

Например, одномерная струна по которой едет квазипрямоугольный импульс. В месте фронта и спада этого импульса количество точек одномерной решётки должно быть очень большим, а в остальных (пустых) местах -- очень малым. Едет "прямоугольник", а вместе с ним перестраивается и густота точек решётки.

28
Сегодня обнаружил, что кроме этого форума и коровника ещё есть, например вот этот: http://zx.oberon2.ru/forum/

29
Общий раздел / Оверклокинг
« : Май 11, 2012, 09:32:48 am »
Вчера ради спортивного интереса включил в асусовском биосе опцию OC Tuning (Overclock Tuning). Перезагрузившись пару раз компьютер сам настроился на множитель турбо буста 43 и частоту шины где-то в районе 103 МГц (Core i7 2600K, ASUS P6Z68 V LE, Kingston 4*4 Гб 1333 МГц).

Выглядит это так. Пока ничего вычислять не надо процессор работает на частоте 1600 МГц. Как только запускаешь процессороёмкую программу включается турбо буст и проц сам гонится примерно до 4.5 ГГц. Невооружённым глазом заметно, что компьютер становится более отзывчивым (летает).

Замерил производительность сортировкой:


Правда радость от того что компьютер "летает" была недолгой...

После баловства с сортировкой я запустил серьёзную программу (365/7/24) под большой нагрузкой надолго. Минут через пятнадцать она сдохла -- "не отвечает". Пришлось снизить множитель турбо буста до 42. Серьёзная программа проработала дольше, но всё равно сдохла. Снизил до 41. Проработала ещё дольше, но тоже сдохла. Снизил до 40. Работала гораздо дольше, но опять сдохла. Снижать множитель до 39 уже выгоды особой нет, а сдохнуть может.

Короче пользы от оверклокинга не оказалось совершенно никакой: программы которые выполняются за минуту ускорять особого смысла нет, а серьёзные программы которые должны под большой нагрузкой работать по формуле 365/7/24 ускорять не получается ибо они через некоторое время дохнут.

Это ещё не всё. Мало того что нет пользы, так есть ещё и вред. Когда процессор начинает совершать ошибки, то портятся все программы, а не только та которая много думает. В частности портится сама Виндос. В течение одного дня Виндовс у меня слетела два раза (после перезагрузки компьютера Виндовс не смогла сама загрузиться). На этом беды не кончились. Во время этих "турбо-бустов" у меня была запущена MS Visual Studio 2008, вот она тоже сама себя запорола и, видимо, придётся её переустанавливать (не открывает проекты зараза). Какие ещё разрушения были вчера причинены системе я пока не понял.

30
Некоторые программы запущенные под 32 разрядной Mono 2.6.7 могут работать до пяти раз медленнее чем запущенные под 64 разрядной микрософтовской реализации в Windows 7

 :o :o :o


Страницы: 1 [2] 3