|
Ещё пара слов про магические квадраты
|
07:35
|
|---|
|
Напишу ещё немного про магические квадраты, рассмотрение которых было начато здесь. Тема сия обширна, а потому, думаю, что она станет основой для моей очередной научно-популярной статьи, в коих я рассказываю о преимуществах функционального программирования над прочими подходами. Здесь же хочу зафиксировать некоторые интересные результаты, достигнутые в процессе оптимизации вычислений. Дело в том, что переборы бываю разные, а потому можно использовать те или иные ограничения для отсекания неныжных ветвей перебора, которые заведомо не приведут к должному результату.
После некоторого раздумья над тем, как можно оптимизировать переборный процесс, было найдено некоторое промежуточное решение, которое и представлено здесь. Необходимо отметить, что предыдущий алгоритм для осуществления перебора использовал понятие перестановки, поэтому самый внешний цикл работал именно по всем перестановкам для n2, что влекло за собой комбинаторный взрыв. Однако, если подумать, нет никакого смысла разбирать перестановки, у которых первые n чисел не составляют в сумме магическое число. То же самое справедливо и для остальных n-ок. Поэтому внешний цикл необходимо устраивать по размещениям из n2 по n, отсекая на этом этапе ненужные комбинации. Итого получилось достаточно прилично:
( Немного исходного кода )
Главная функция здесь — arrangements, именно она вычисляет список размещений. Впрочем, она работает по тому же принципу, что и функция permutations, поэтому останавливать на ней своё внимание не сто́ит. Более интересна функция constructSquares, которая конструирует квадраты, среди которых ищутся магические. Конструирование производится по принципу, который обуславливает равенство сумм каждой n-ки магической сумме. Далее каждый квадрат проверяется на магичность уже́ разработанным способом.
В итоге получилось весьма интересно. Как видно, в целях сравнения был оставлен и предыдущий алгоритм. Функция getMagicSquares работает по старому алгоритму, а функция getMagicSquares' — по новому. Эти функции были запущены для аргумента 3 и выдали одинаковые результаты (что абсолютно прогнозировалось). Но времена, которые они затратили на вычисления, поражают: 28.98 секунд против 1.13 секунд. Итого имеем 25-кратное преимущество нового алгоритма, основанного на размещениях, перед старым.
( Ещё немного статистики )
|
|
Ещё некоторые предложения по ТСДНЭ
|
09:01
|
|---|
|
Подумалось мне тут намедни. Ежели актуальность ТСДНЭ достаточно высока (в течение выходных получил с десяток благодарственных отзывов по почте от совершенно неангажированных людей), то может быть имеет смысл расширить область деятельности и начать заниматься переводом словарных статей Словаря на английский язык (а позже можно будет подумать и над другими актуальными языками). Правда, оценить востребованность такого перевода будет сложно, но тем не менее, в западных странах окромя обывателя с проветренными мозгами ещё есть люди, которые называют вещи своими именами.
Кто возьмётся?
|
|
Россия для Русских: Хакасия
|
09:13
|
|---|
|
Пришло время для рассмотрения последней «республики» СФО в рамках проекта «Россия для Русских». Это — Хакасия. Честно говоря, начались какие-то регионы, о которых, видимо, знать-то никто не знает, окромя тех, кто там проживает. Я не могу вспомнить, к примеру, ни одного телевизионного репортажа, который повествовал бы о жизни в Хакасии, даже при осуществлении выборов [ТСДНЭ] там. Тем не менее, такие регионы необходимо рассмотреть в том числе и для развенчания досужей мифологемы «Если Россия для Русских, то...»
Рассмотрим диаграмму распределения крупных этнических групп в Хакасии:
Табличное представление информации:
| Русские |
438 395 |
83.92 % |
| Хакасы |
65 421 |
12.52 % |
| Немцы |
9 161 |
1.75 % |
| Украинцы |
8 360 |
1.60 % |
| Шорцы |
1 078 |
0.21 % |
| ВСЕГО |
522 415 |
100.00 % |
В общем, всё и так видно...
|
|
|
![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small}
_darkus_