ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 19 из 20
  19  все
Пятничная задачка для ума за 1 миллион $
    #39533080
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
Aleksandr Sharahovasutp2пропущено...

пропущено...

пропущено...

Сравниваешь Integer с Integer, но первый Integer приводишь к Cardinal? Точно индусы курят нервно в стороне)))))

Для переменных типа integer этот код эквивалентен такому
Код: pascal
1.
if (c>=BoardSize) or (c<0) or (r>=BoardSize) or (r<0) then exit;



Да неужели. На основании каких таких размышлений ты пришел к такому выводу? наверное когда писал свои бредовые опусы?

Aleksandr SharahovИди лечи свои комплексы.Повторяешься насчет комплексов. У кого что болит, тот о том и говорит?
...
Рейтинг: 0 / 0
08.10.2017, 21:52
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533083
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2Йоу, посмотрел код по ссылке. Жесть.

Код: pascal
1.
2.
3.
4.
5.
const
  MaxBoardSize= 100000;
  CountCol: array[0..MaxBoardSize-1] of byte;   
  CountRow: array[0..MaxBoardSize-1] of byte;  
  CountDiagP: array[0..2*MaxBoardSize-2] of byte;

реально что ли используются статические массивы такого размера?

Реально. Один из способов получить быстрый код на Delphi.
На динамических придется дополнительно напрягаться, чтобы получить ту же скорость.
Нет смысла для учебной задачи.


asutp2
Код: pascal
1.
begin;

што?

В сад. Узбагойся.


asutp2
Код: pascal
1.
2.
label
  NEXT1, NEXT2, NEXT3, PROC1, PROC2, PROC3, BACK1, BACK2, BACK3, FINISH;

на turbo pascal что ли пишешь?)

Чукча не читатель? Это трансляция C-кода одного японца.

asutp2Не увидел по ссылке обсуждаемую выше функцию. Протухшая версия?
Эта функция не требуется для поиска решения.
Использую ее только для проверки найденного решения.

Но ты напишешь все свое, ведь правда?
...
Рейтинг: 0 / 0
08.10.2017, 21:59
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533086
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2Aleksandr SharahovДля переменных типа integer этот код эквивалентен такому
Код: pascal
1.
if (c>=BoardSize) or (c<0) or (r>=BoardSize) or (r<0) then exit;



Да неужели.


Еще одна двойка за домашку.
...
Рейтинг: 0 / 0
08.10.2017, 22:05
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533094
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
:facepalm: :facepalm: :facepalm:
...
Рейтинг: 0 / 0
08.10.2017, 22:27
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533095
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2,

где обещанные ошибки, эмоциональный ты наш?
...
Рейтинг: 0 / 0
08.10.2017, 22:36
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533102
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну вы и нудные оба. Тема - ферзи. Давайте обсуждать ферзей йопта...
...
Рейтинг: 0 / 0
08.10.2017, 23:08
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533107
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

Несмотря ни на что, есть определенная польза и от споров с нубами. Вот он затронул распараллеливание. Надо будет отразить в статье. Тут вскользь упоминалось уже, что это делается разложением по строке (строкам), вроде вычисления определителя матрицы. Кстати, у японца такая опция была. Но подход общий, годится и для поиска завершений.
...
Рейтинг: 0 / 0
08.10.2017, 23:19
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533121
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Специально для господ-теоретиков я опубликовал несколько полных генераций ферзевой расстановки
для досок с 8х8 до 15х15 здесь https://sourceforge.net/p/chess-experiments/code/HEAD/tree/trunk/mayton/queen-problem/out/

Анализируйте. Пользуйтесь.
...
Рейтинг: 0 / 0
09.10.2017, 00:55
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533124
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahovmayton,

Несмотря ни на что, есть определенная польза и от споров с нубами. Вот он затронул распараллеливание. Надо будет отразить в статье. Тут вскользь упоминалось уже, что это делается разложением по строке (строкам), вроде вычисления определителя матрицы. Кстати, у японца такая опция была. Но подход общий, годится и для поиска завершений.
Какая польза от расчета определителя для нашей задачи? Это просто красивый пример который показыват
как работает мультипоточность с immutable-данными а работает она с ними отлично. Ты попробуй натянуть
сферическую мультипоточность на нашу задачу.

В нашей задаче что важно?
1) Для поиска случайного остаточного решения 1000х1000 - стартовать 4-8 вычислительных потоков с разными значениями
Random::seed. Далее все остальное сделает генератор случайности.
2) Для генерации всех остаточных решений 1000х1000. Для рекурсии. Грамотно распределить задания между 4-8 вычислительными
потоками в executor. Каждое задание - дочерняя ветка от родительской вершины. Самих заданий может быть во много раз
больше чем потоков вычисления. Поэтому большинство заданий будет стоять на паузе и ждать освобожения пула потоков.
Таковы реалии для нашего железа.

P.S. И что это такое "отразить в статье" ? Ты что журналист? Код давай...
...
Рейтинг: 0 / 0
09.10.2017, 01:18
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533146
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
asutp2Aleksandr Sharahovпропущено...


Для переменных типа integer этот код эквивалентен такому
Код: pascal
1.
if (c>=BoardSize) or (c<0) or (r>=BoardSize) or (r<0) then exit;


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

PS: хотя читерство, в пром-коде конечно лучше такое не применять, эту оптимизацию должен делать компилятор


mayton,
оч хорошо параллелится задача, диапазоны выдал потокам и всё
...
Рейтинг: 0 / 0
09.10.2017, 06:18
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533159
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
kealon(Ruslan)asutp2пропущено...

Да неужели. На основании каких таких размышлений ты пришел к такому выводу? наверное когда писал свои бредовые опусы?
читаем чем отличается "больше" от "выше", "меньше" от "ниже" и формат представления отрицательных чисел
читаем ВСЕ :) потом смотрим сгенерированный компилятором код для if Integer>=Integer, потом смотрим код для if Cardinal(Integer)>=Integer и сравниваем
...
Рейтинг: 0 / 0
09.10.2017, 07:36
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533173
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
asutp2,
правильнее конечно обе части приводить, иначе поведение может быть очень странным в зависимости от компилятора
...
Рейтинг: 0 / 0
09.10.2017, 08:46
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533259
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
kealon(Ruslan)правильнее конечно обе части приводить, иначе поведение может быть очень странным в зависимости от компилятора

Совершенно верно. Именно так и предлагается делать в статье по ссылке, которую я приводил. При этом компилятор Delphi сгенерирует более эффективный код. На скорость поиска решений эта неточность не повлияет, т.к. код вызывается лишь один раз для проверки единственного найденного решения.

Надо отметить, что еще одна тонкость: в этом коде неявно предполагается, что BoardSize>0. В данном случае это допустимо, т.к. на входе во все процедуры поиска верхнего уровня стоит даже более строгая проверка на BoardSize>=4.
...
Рейтинг: 0 / 0
09.10.2017, 10:51
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533270
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonВ нашей задаче что важно?
1) Для поиска случайного остаточного решения 1000х1000 - стартовать 4-8 вычислительных потоков с разными значениями
Random::seed. Далее все остальное сделает генератор случайности.
2) Для генерации всех остаточных решений 1000х1000. Для рекурсии. Грамотно распределить задания между 4-8 вычислительными
потоками в executor. Каждое задание - дочерняя ветка от родительской вершины. Самих заданий может быть во много раз
больше чем потоков вычисления. Поэтому большинство заданий будет стоять на паузе и ждать освобожения пула потоков.
Таковы реалии для нашего железа.


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

maytonP.S. И что это такое "отразить в статье" ? Ты что журналист? Код давай...

Да и это тоже. Код будет, разумеется. Но параллельно приходится оттачивать стиль изложения. У одержимых поиском ошибок становится модным трендом цепляться не только к оформлению кода, но и к словам.
...
Рейтинг: 0 / 0
09.10.2017, 11:06
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533375
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
Aleksandr Sharahov,

ты видимо из тех, кто любую критику, даже конструктивную, считаешь личным оскорблением, не?

Что касается спорного момента - сгенерированный код на асме подтверждает твои слова, что Cardinal(Integer)>=Integer работает быстрее чем Integer>Integer?
...
Рейтинг: 0 / 0
09.10.2017, 13:15
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533387
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2Aleksandr Sharahov,

ты видимо из тех, кто любую критику, даже конструктивную, считаешь личным оскорблением, не?

Что касается спорного момента - сгенерированный код на асме подтверждает твои слова, что Cardinal(Integer)>=Integer работает быстрее чем Integer>Integer?

Спасибо за найденную неточность в сообщении, опубликованном на данном форуме.

С правильным применением быстрой проверки попадания точки в диапазон вы можете ознакомиться по ранее данной вам ссылке в статье.

Конструктивная критика приветствуется.
...
Рейтинг: 0 / 0
09.10.2017, 13:32
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533393
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
Aleksandr SharahovС правильным применением быстрой проверки попадания точки в диапазон вы можете ознакомиться по ранее данной вам ссылке в статье.

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

Покажи код, и если я не прав, то я это признаю.
...
Рейтинг: 0 / 0
09.10.2017, 13:41
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533417
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2, смотри:

В условиях, что все переменные имеют тип integer и BoardSize>0
нам надо выполнить такую проверку:
Код: pascal
1.
if (c>=BoardSize) or (c<0) or (r>=BoardSize) or (r<0) then exit;



утверждается, что достаточно проверить такое:
Код: pascal
1.
2.
if (cardinal(c)>=cardinal(BoardSize)) 
or (cardinal(r)>=cardinal(BoardSize)) then exit;



Причем потери скорости не произойдет, т.к. расширение типа не потребуется.

Чтобы трюк работал, достаточно, чтобы длина диапазона (в нашем случае 0..BoardSize) не превышала половины всего целочисленного диапазона.
...
Рейтинг: 0 / 0
09.10.2017, 13:58
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533430
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahovasutp2, смотри:

В условиях, что все переменные имеют тип integer и BoardSize>0
нам надо выполнить такую проверку:
Код: pascal
1.
if (c>=BoardSize) or (c<0) or (r>=BoardSize) or (r<0) then exit;



утверждается, что достаточно проверить такое:
Код: pascal
1.
2.
if (cardinal(c)>=cardinal(BoardSize)) 
or (cardinal(r)>=cardinal(BoardSize)) then exit;



Причем потери скорости не произойдет, т.к. расширение типа не потребуется.

Чтобы трюк работал, достаточно, чтобы длина диапазона (в нашем случае 0..BoardSize) не превышала половины всего целочисленного диапазона.
Не силен в паскале, но если cardinal(Integer) это тоже самое что в C (unsigned int) int, то все верно. Т.к. процессором никаких преобразований операндов не делается, а просто компилятором используется команда беззнакового сравнения.
У знаковых целых знак хранится в старшем бите, 1 - отрицательное, поэтому при таком "преобразовании" положительные значения не меняются, а отрицательные всегда станут больше максимально возможного знакового положительного.
...
Рейтинг: 0 / 0
09.10.2017, 14:17
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533452
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
Ок, накидал небольшую процедуру:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
procedure TForm4.Button1Click(Sender: TObject);
var
  I1, I2, T: Integer;
begin
  I1 := 10;
  I2 := 5;
  if I1 >= I2 then
    T := 1;
  if Cardinal(I1) >= I2 then
    T := 1;
  if Cardinal(I1) >= Cardinal(I2) then
    T := 3;
  Button1.Caption := IntToStr(T);
end;



Теперь смотрим, что же генерит делфи 10.1 berlin:
Unit4.pas.30: I1 := 10;
005C9CC3 C745F80A000000 mov [ebp-$08],$0000000a
Unit4.pas.31: I2 := 5;
005C9CCA C745F405000000 mov [ebp-$0c],$00000005
Unit4.pas.32: if I1 >= I2 then
005C9CD1 8B45F8 mov eax,[ebp-$08]
005C9CD4 3B45F4 cmp eax,[ebp-$0c]
005C9CD7 7C07 jl $005c9ce0
Unit4.pas.33: T := 1;
005C9CD9 C745F001000000 mov [ebp-$10],$00000001
Unit4.pas.34: if Cardinal(I1) >= I2 then
005C9CE0 8B45F8 mov eax,[ebp-$08]
005C9CE3 33D2 xor edx,edx
005C9CE5 52 push edx
005C9CE6 50 push eax
005C9CE7 8B45F4 mov eax,[ebp-$0c]
005C9CEA 99 cdq
005C9CEB 3B542404 cmp edx,[esp+$04]
005C9CEF 7509 jnz $005c9cfa
005C9CF1 3B0424 cmp eax,[esp]
005C9CF4 5A pop edx
005C9CF5 58 pop eax
005C9CF6 770D jnbe $005c9d05
005C9CF8 EB04 jmp $005c9cfe
005C9CFA 5A pop edx
005C9CFB 58 pop eax
005C9CFC 7F07 jnle $005c9d05
Unit4.pas.35: T := 1;
005C9CFE C745F001000000 mov [ebp-$10],$00000001
Unit4.pas.36: if Cardinal(I1) >= Cardinal(I2) then
005C9D05 8B45F8 mov eax,[ebp-$08]
005C9D08 3B45F4 cmp eax,[ebp-$0c]
005C9D0B 7207 jb $005c9d14
Unit4.pas.37: T := 3;
005C9D0D C745F003000000 mov [ebp-$10],$00000003
Unit4.pas.38: Button1.Caption := IntToStr(T);
005C9D14 8D55E8 lea edx,[ebp-$18]

Хорошо видно, к чему приводит смешивание разных типов (хотя при этом они имеют одинаковую размерность)...
...
Рейтинг: 0 / 0
09.10.2017, 14:46
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533468
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2Хорошо видно, к чему приводит смешивание разных типов (хотя при этом они имеют одинаковую размерность)...

Почему не написать в конструктивном ключе:

Идея верная и при правильном применении позволит выполнить необходимую проверку, уменьшив число сравнений в 2 раза. И даже если при реализации допустить неточность, которую мы обсуждаем уже 2 дня, будет потеряно не более 20 тактов CPU.
...
Рейтинг: 0 / 0
09.10.2017, 14:59
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533542
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
А может разница в настройках компилятора? Всё же как легко оказалось затролить Александра.
...
Рейтинг: 0 / 0
09.10.2017, 16:28
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533552
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
asutp2
Участник
exp98,

я не тролил Александра и не собирался. У меня просто возникло сомнения правильности использования конкретных конструкций и не более того. Когда сделает реальный алгоритм, решающий задачу топика, будет реально круто.
...
Рейтинг: 0 / 0
09.10.2017, 16:35
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533597
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
asutp2У меня просто возникло сомнения правильности использования конкретных конструкций и не более того.

Тебе сто раз повторили: если интересно, как правильно использовать - смотри статью, а не придирайся к сообщениям на форуме, где у каждого полно неточностей, опечаток, оговорок привязок к контексту и т.п.

И вместо этого ты второй день продолжаешь мусолить абсолютно ни на что не влияющую неточность. Зачем?
...
Рейтинг: 0 / 0
09.10.2017, 17:26
| Ответить | Цитировать | Написать  
Пятничная задачка для ума за 1 миллион $
    #39533668
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги. Ассемблер и его тонкости нисколько не помогают в данной задаче.
Она - математична по своей природе. А ассемблер просто нас уводит в глухой
Оффтопик.
...
Рейтинг: 0 / 0
09.10.2017, 19:56
| Ответить | Цитировать | Написать  
25 сообщений из 491, страница 19 из 20
  19  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]