Неархитектурная задачка

[vlad]

На моей тачке решение от vlad тоже работает примерно в два раза быстрее решения от Сергея.
0.312 против 0.68

Э-э-э, от рекурсии что ли попробовать избавиться?..  Как раз наверное в два раза и ускорится...

У меня есть рекурсия И вообще код без изысков и каких-то мощных абстракций, но и без явной оптимизации. Вполне такой "каждодневный". Я его оставлю такой как есть, пока все кто хотел решения не предоставят. Потом можно будет пооптимизировать.

[Губанов Сергей Юрьевич]

Рекурсию оставил, но врукопашную раскрыл цикл for (int value = 1; value < 10; value++) на девять ифов. Дотнетный компилятор этого сам не делает. Код, конечно, стал индусским, но работать стало в два раза быстрее -- 0.0628 секунды на i7 2600K (без оверклокинга) под Windows 7. Встроил высокоточный таймер (точность порядка 1 микросекунды). Ещё при старте печатаю разрядность используемого дотнетного рантайма.

Use 64 bit runtime
Initialization...
Source:
000000018
009030000
070000000
800100000
000007300
200000000
030000960
100480000
000200000

Result:
dt = 0.0627798907917168 seconds
342976518
689531427
571842639
853194276
914627385
267358194
438715962
126489753
795263841
Press 'Enter' to exit

Прикладываю дотнетный экзешник и зазипованный исходник

[vlad]

Поскольку время может зависеть от входных данных, то я сгенерировал 12 вариантов (http://kjell.haxx.se/sudoku/).
Видно, что моя программа хорошо "висит" на одном из них.
Итоговое время ~16 секунд.

[Peter Almazov]

Я допустил ошибку - запускал программу Сергея из студии. Если запускать не из студии, то работает значительно быстрее.
Целевая платформа .NET 2.0.
Вот уточненные данные.

Влад: 0.312
Сергей, старый вариант: 0.390
Сергей, индусский вариант: 0.187

[valexey]

Я допустил ошибку - запускал программу Сергея из студии. Если запускать не из студии, то работает значительно быстрее.
Целевая платформа .NET 2.0.
Вот уточненные данные.

Влад: 0.312
Сергей, старый вариант: 0.390
Сергей, индусский вариант: 0.187

Я тут на Go набыдлокодил. Оно пока кривое и глючное, и вообще без оптимизций в плане программинга, то есть без низкоуровневых штучек, не используя unsafe фичи. Получил такое:

Код: [Выделить]

$ time ./go
Game finished
3 4 2 9 7 6 5 1 8
6 8 9 5 3 1 4 2 7
5 7 1 8 4 2 6 3 9
8 5 3 1 9 4 2 7 6
9 1 4 6 2 7 3 8 5
2 6 7 3 5 8 1 9 4
4 3 8 7 1 5 9 6 2
1 2 6 4 8 9 7 5 3
7 9 5 2 6 3 8 4 1

real 0m0.081s
user 0m0.076s
sys 0m0.003s

Это на том же макбуке. С учетом того, что go'шный референсный компилятор оптимизирует крайне хреново (на порядок хуже чем gccgo) а у меня алгоритм сейчас найдя решение даже не прекращает работать, я думаю что у меня где-то ошибка, вследствие которой алгоритм работает быстрее и случайно так оказалось, что на этих входных данных он работает правильно.

[valexey]

А если сделать выход по окончанию решения, то тайминги такие:

Код: [Выделить]

real 0m0.068s
user 0m0.063s
sys 0m0.003s


[valexey]

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

Код: [Выделить]

real 0m0.021s
user 0m0.018s
sys 0m0.002s

А у меня такой:

Код: [Выделить]

real 0m2.295s
user 0m2.286s
sys 0m0.008s

Но несмотря на это мое чудовище работает тут все равно корректно, что очень странно.

[valexey]

Допилил решение на Go до состояния когда оно может на вход принимать задачи в стандартном формате (см. в каком формате владовы 12ть задач). Программа работает полностью аналогично владовой (на stdin принимает задачи, на stdout выдает решения), только в конце оно не печатает сколько времени заняло. Так что советую пользоваться утилитой time.

Прикладываю исполняемый файл собранный под макось (mac os 10.7 lion 64 bit). Ибо других осей под рукой просто нет :-)

12ть этих задачек владова программа прожевывает за 19 секунд, моя программа - за 6 секунд. Решения идентичные.

[Губанов Сергей Юрьевич]

Тоже допилил на чтение файла in.txt

На моём компе:
программа Влада -- 14 секунд
моя (индусская) программа -- 8.43 секунды

[valexey]

Тоже допилил на чтение файла in.txt

На моём компе:
программа Влада -- 14 секунд
моя (индусская) программа -- 8.43 секунды

Откомпилированная тобой программа на меня страшно ругается при запуске

Код: [Выделить]

$ mono ./Sudoku.exe < tasks.txt

Unhandled Exception: System.TypeInitializationException: An exception was thrown by the type initializer for Unix_librt ---> System.DllNotFoundException: /lib/librt.so.1
  at (wrapper managed-to-native) Sudoku.Program/Clock/Unix_librt:clock_gettime (int,Sudoku.Program/Clock/Unix_librt/Time&)
  at Sudoku.Program+Clock+Unix_librt.GetSeconds () [0x00000] in <filename unknown>:0
  at Sudoku.Program+Clock+Unix_librt..cctor () [0x00000] in <filename unknown>:0
  --- End of inner exception stack trace ---
  at Sudoku.Program+Clock.GetSeconds () [0x00000] in <filename unknown>:0
  at Sudoku.Program.Main (System.String[] args) [0x00000] in <filename unknown>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.TypeInitializationException: An exception was thrown by the type initializer for Unix_librt ---> System.DllNotFoundException: /lib/librt.so.1
  at (wrapper managed-to-native) Sudoku.Program/Clock/Unix_librt:clock_gettime (int,Sudoku.Program/Clock/Unix_librt/Time&)
  at Sudoku.Program+Clock+Unix_librt.GetSeconds () [0x00000] in <filename unknown>:0
  at Sudoku.Program+Clock+Unix_librt..cctor () [0x00000] in <filename unknown>:0
  --- End of inner exception stack trace ---
  at Sudoku.Program+Clock.GetSeconds () [0x00000] in <filename unknown>:0
  at Sudoku.Program.Main (System.String[] args) [0x00000] in <filename unknown>:0


[valexey]

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

[valexey]

Угу. Выпилил измерялку - заработало.
Пара пожеланий:
1) Очень хочется чтобы программа хавала из stdin столько задач сколько там есть, а не только первую. И последовательно их решала. Меряем время за всю серию задач разом. Можно внешней тулзой.
2) Выдаем решение сплошным потоком. Пример вывода:

Код: [Выделить]

571248936
482396517
936751284
265437891
347189652
198562743
823615479
654973128
719824365
172869543
694531278
538742169
345186792
721953486
986274315
813627954
459318627
267495831
Это удобно тем, что можно автоматически находить различия в решениях разных программ (тупо diff'ом).

[valexey]

Мдя. А под макось только 32битная моно есть. Точнее есть и 64битная, но ее нужно руками компилировать.
Пойду домой, попробую все то же позапускать на 32битном линуксе. Там будут 32битными все, так что все честно.

[Илья Ермаков]

Таки шо, уже исходниками начинаем меряться?

[vlad]

Таки шо, уже исходниками начинаем меряться?

Не, еще рано, еще желающие есть предоставить решение.