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

[Valery Solovey]

1) Очень хочется чтобы программа хавала из stdin столько задач сколько там есть, а не только первую.

А в каком виде получение исходных данных должно быть? Очень желательно, чтобы алгоритм получения задачи был у всех одинаковый. Чтобы мерять только сам процесс решения головоломки.

[valexey]

1) Очень хочется чтобы программа хавала из stdin столько задач сколько там есть, а не только первую.

А в каком виде получение исходных данных должно быть? Очень желательно, чтобы алгоритм получения задачи был у всех одинаковый. Чтобы мерять только сам процесс решения головоломки.

В том виде в котором выдает сайт http://kjell.haxx.se/sudoku/
То есть в таком:

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

57.!...!...
.82!...!...
...!..1!..4
---!---!---
..5!...!8..
3..!..9!...
...!...!7..
---!---!---
..3!...!..9
...!.7.!...
.1.!82.!...
...!.6.!...
..4!.31!...
5..!..2!..9
---!---!---
...!...!...
7..!9..!...
..6!...!31.
---!---!---
.13!...!...
...!...!..7
...!4..!8..
...!..3!6..
.5.!...!...
84.!.1.!...
---!---!---
...!1.7!...
...!...!..4
..2!...!.85
---!---!---
...!...!...
...!58.!..1
..6!...!7..
.1.!...!...
...!.2.!..7
.85!...!..9
---!---!---
...!...!.5.
...!.39!...
...!...!814
---!---!---
7..!...!...
...!8.5!...
3..!...!.6.
...!..7!4..
.8.!.1.!...
...!.62!...
---!---!---
...!9..!5..
2..!...!...
1.6!...!...
---!---!---
.5.!8..!...
...!...!.67
..1!...!..2
...!9..!...
..7!...!2..
.9.!8..!...
---!---!---
38.!...!...
...!...!4..
...!..2!7.5
---!---!---
...!1..!.38
..5!.4.!...
...!...!.9.
...!.2.!5..
...!...!.9.
.4.!1..!...
---!---!---
3..!...!2..
...!6..!.8.
5..!..9!...
---!---!---
...!.35!...
.1.!...!.4.
.6.!.8.!...
...!7..!...
..4!...!..5
...!.6.!...
---!---!---
.7.!...!...
...!.5.!..9
.1.!2..!.3.
---!---!---
..9!..4!...
...!6..!71.
.25!...!...
8.3!...!...
...!5.6!9..
...!...!7..
---!---!---
.5.!..9!..3
...!.1.!.4.
...!...!..8
---!---!---
...!.8.!...
49.!...!5..
...!...!..1
.1.!...!62.
...!3..!8..
..7!.5.!...
---!---!---
...!...!...
6..!..8!...
..5!...!.47
---!---!---
...!...!...
...!.71!..9
38.!...!...
...!...!.69
5..!.74!...
...!.5.!..1
---!---!---
...!...!4..
..1!...!...
.83!6..!...
---!---!---
4..!...!.2.
...!1..!.3.
.7.!...!...
3.7!...!2..
...!8.1!..6
2..!...!...
---!---!---
...!73.!5..
...!...!...
.8.!...!..9
---!---!---
...!6.9!..4
...!...!.3.
...!..8!...
Пока у всех алгоритмы тормозные настолько, что производительность IO роли не играет.

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

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

У тебя там цикл дейкстры что ли?

[valexey]

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

У тебя там цикл дейкстры что ли?

У меня ощущение, что Илья когда настанет время открывать исходники, с аццким хохотом покажет нам слип в своем коде. После удаления оного слипа программа ускорится в 1000 раз.

PS. А вообще мало ли. Вдруг у него там строится множество всех возможных (доступных) комбинаций, а затем идет просто поиск нужной. Тогда тормоз только при запуске будет, а в дальнейшем работать будет очень-очень быстро.

[valexey]

Вот бинарь версии на Go под линукс.

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

Убрал таймер неработающий под макосью. Сделал вывод ответа как у Влада. Ещё самую малость удалось соптимизировать.

На оверклоченном до 4200 МГц i7 3770K на том файле in.txt получилось:

программа Влада -- 12.26 секунд,
моя программа -- 6.70 секунд.

Ещё сильнее уже не оптимизируется. Надо придумывать какую-то совсем другую эвристику.

[valexey]

Убрал таймер неработающий под макосью. Сделал вывод ответа как у Влада. Ещё самую малость удалось соптимизировать.

На оверклоченном до 4200 МГц i7 3770K на том файле in.txt получилось:

программа Влада -- 12.26 секунд,
моя программа -- 6.70 секунд.

Ещё сильнее уже не оптимизируется. Надо придумывать какую-то совсем другую эвристику.

Погонял на 32битном линуксе то что ты сейчас прислал и то что влад присылал а также свою прогу гошную. Итого для пакета из 12ти задач:

Приложение влада:

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

real    0m24.645s
user    0m24.566s
sys     0m0.056s

Твое приложение:

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

real    0m20.002s
user    0m19.945s
sys     0m0.036s

Мое приложение:

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

real    0m10.847s
user    0m10.757s
sys     0m0.064s

Если что, процессор такой:

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

cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Duo CPU     T7250  @ 2.00GHz
stepping        : 13
cpu MHz         : 800.000
cache size      : 2048 KB

PS. Подозреваю, что программа Влада у тебя работает медленно просто потому, что собрана под 32 бита.

[vlad]

Ну раз пошла такая пьянка... Ускорил в ~3 раза. Код не оптимизил, поменял алгоритм чуть-чуть.

[Peter Almazov]

Убрал таймер неработающий под макосью.

Сергей, попробуй System.Diagnostics.Stopwatch под линуксом. Под виндой он работает так же, как твой таймер с высоким разрешением. Я под линуксом не могу проверить, во всяком случае, малой кровью.

[Kemet]

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

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

Ну раз пошла такая пьянка... Ускорил в ~3 раза. Код не оптимизил, поменял алгоритм чуть-чуть.

Пока не успел уйти на работу померил на домашнем компе:

новая программа Влада -- 3.59 сек
моя индусская программа -- 6.70 сек

Я так понял, на текущий момент программы vlad и valexey на одинаковых машинах будут работать примерно с одинаковой скоростью, а моя будет в ~2 раза медленнее.

[valexey]

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

Оу! Да у тебя будет практически решение на хаскелле! :-)

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

Сергей, попробуй System.Diagnostics.Stopwatch под линуксом.

Попробовал, работает.

Ломаю голову над новой эвристикой... Подумалось, что если сортировать пустые клетки по признаку допустимых вариантов и сначала рекурсивиться в те где свободных вариантов меньше всего, то дерево будет менее ветвистое и как бы быстрее обойдётся. Оказалось нет. Сортируй не сортируй (или даже сортируй наоборот), а количество рекурсивных вызовов остаётся постоянным: 701 миллион на том тестовом файле.

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

Ломаю голову над новой эвристикой... Подумалось, что если сортировать пустые клетки по признаку допустимых вариантов и сначала рекурсивиться в те где свободных вариантов меньше всего, то дерево будет менее ветвистое и как бы быстрее обойдётся. Оказалось нет. Сортируй не сортируй (или даже сортируй наоборот), а количество рекурсивных вызовов остаётся постоянным: 701 миллион на том тестовом файле.

БЛИН!!! БЛИН!!! БЛИН!!! Я опять совершил свою любимую ошибку! Написав процедуру нигде её не вызвал и недоумеваю почему лучше не стало! А раз лучше все равно не стало выдал "военную тайну" самого быстрого алгоритма 

Короче теперь программа летает со скоростью света. Общее количество рекурсивных вызовов сократилось с 701M до 375K.

Все тесты из in.txt расщёлкиваются за 0.175 секунды.

[valexey]

Ломаю голову над новой эвристикой... Подумалось, что если сортировать пустые клетки по признаку допустимых вариантов и сначала рекурсивиться в те где свободных вариантов меньше всего, то дерево будет менее ветвистое и как бы быстрее обойдётся. Оказалось нет. Сортируй не сортируй (или даже сортируй наоборот), а количество рекурсивных вызовов остаётся постоянным: 701 миллион на том тестовом файле.

БЛИН!!! БЛИН!!! БЛИН!!! Я опять совершил свою любимую ошибку! Написав процедуру нигде её не вызвал и недоумеваю почему лучше не стало! А раз лучше все равно не стало выдал "военную тайну" самого быстрого алгоритма 

Короче теперь программа летает со скоростью света. Общее количество рекурсивных вызовов сократилось с 701M до 375K.

Все тесты из in.txt расщёлкиваются за 0.175 секунды.

Это не военная тайна - у меня оно так и работало изначально (убрав эту эвристику я получил время работы приложения 20 минут на тестовом пакете задач, то есть примерно в 200 раз медленней). Низкоуровневыми оптимизациями заниматься пока не интересно, поэтому я буду совершенствовать именно алгоритм а не реализацию.