Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Ruby: Общие вопросы > Аномалия в матрице


Автор: kolpeex1 11.3.2010, 19:19
Предыстория: По электронике необходимо оптимизировать большие логические выражения. В-общем, оптимизировать-то я оптимизировал, а вот проверять лень, поскольку выражений четыре (два раза: оригинал и оптимизированное), входов X - 8. Т.е. для каждого выражения надо высчитать 256 комбинаций битов X. Итого: 2048 умственных расчётов.
Решил всё сделать синтетический тест на Ruby.

Проблема: Чтобы делать много проверок для всех комбинаций решил сделать массив этих самых комбинаций (т.е. матрицу). Примерно так:
Код

  комбинация 1:   0 0 0 0 0 0 0 0
  комбинация 2:   0 0 0 0 0 0 0 1
...
  комбинация 256: 1 1 1 1 1 1 1 1

Написал алгоритм, который должен заполнить пустую матрицу 256x8 нужными значениями. (Заполняется первый столбец наполовину нулями, наполовину - единицами. 0011. Следующий по четверти, но уже два раза. 0101)
*** размеры матрицы и значений поменял на меньшие для удобства. С нужными размерами тоже самое.
Код

x_from = 0
x_to = 2
values = [0, 1]

variants = density = values.size ** (x_to - x_from + 1)
repeat = 1

tests = Array.new variants, (Array.new ((x_to - x_from + 1), 0))


for x in (x_from)..(x_to)
  density = density / values.size
  y = 0
  repeat.times {
    values.each {|b|
      density.times {
        tests[y][x] = b
        print y.to_s + ':' + x.to_s + ' = ' + tests[y][x].to_s + "\n"
        y = y + 1
      }
    }
  }
  repeat = repeat * values.size
end


Работает цикл столько, сколько надо. Отладка выводит то, что и ожидалось:
Код

0:0 = 0
1:0 = 0
2:0 = 0
3:0 = 0
4:0 = 1
5:0 = 1
6:0 = 1
7:0 = 1
0:1 = 0
1:1 = 0
2:1 = 1
3:1 = 1
4:1 = 0
5:1 = 0
6:1 = 1
7:1 = 1
0:2 = 0
1:2 = 1
2:2 = 0
3:2 = 1
4:2 = 0
5:2 = 1
6:2 = 0
7:2 = 1


Обратите внимание на 
Код

print y.to_s + ':' + x.to_s + ' = ' + tests[y][x].to_s + "\n"

Я вывожу tests[y][x], всё ок. Больше этот элемент я нигде не трогаю.
Т.е. 6:2 = 0, а 7:2 = 1.  smile 

Ставлю теперь строчку
Код

print tests[6][2].to_s + tests[7][2].to_s + "\n"


Что бы вы думали? 
11

Чтобы описать моё состояние, дам ссылку на картинку: http://shattl.org/i/ffuuu.jpg

Я решил, что каким-то образом последнее присвоение случается для всех элементов матрицы. И тогда я немного видоизменил внутренность самого внутреннего цикла.
Код

...
        if x==2 && y==7
          print tests[6][2].to_s + " is "
        end
        tests[y][x] = b
        if x==2 && y==7
          print tests[6][2].to_s + "\n"
        end
...


Что бы вы думали? Компьютер с полной уверенностью пишет, что
0 is 1

Вопрос: Неужели я так сильно хочу спать, что прямо возле носа не вижу своей ошибки?

P.S. tests.each {... утверждает, что все элементы матрицы - единички.

Добавлено через 3 минуты и 26 секунд
Понимаю, что можно в тесте просто чесать от 0 до 255, разделяя i на восемь бит и отдавая их Y-выражениям. Я просто хочу уже разобраться, наконец, с этой аномалией.

Автор: source777 12.3.2010, 01:11
Цитата(kolpeex1 @  11.3.2010,  19:19 Найти цитируемый пост)
x_from = 0
x_to = 2
values = [0, 1]
variants = density = values.size ** (x_to - x_from + 1)
repeat = 1
tests = Array.new variants, (Array.new ((x_to - x_from + 1), 0))
for x in (x_from)..(x_to)
  density = density / values.size
  y = 0
  repeat.times {
    values.each {|b|
      density.times {
        tests[y][x] = b
        print y.to_s + ':' + x.to_s + ' = ' + tests[y][x].to_s + "\n"
        y = y + 1
      }
    }
  }
  repeat = repeat * values.size
end


Какой-то мегагемморойный способ заполнить матрицу нулями и единичками... без пол литра(и отладчика) не разберёшься.
Пожалей людей, которые твой код читать будут!!!

Лично мне первое что пришло в голову для заполнения матрицы всеми возможными комбинациями нулей и единиц по 8 штук - перебрать все числа от 0 до 255:
Код

x = 8
tests = []
(0...2**x).each do |int|
  const = 2**(x-1)
  test = []
  (1..x).each do |i|
    test << ((int & const != 0) ? 1 : 0)
    const = const >> 1
  end
  tests << test
end


Цитата

[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 1, 1]
[0, 0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 1]
[0, 0, 0, 1, 0, 1, 1, 0]
[0, 0, 0, 1, 0, 1, 1, 1]
[0, 0, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 1]
[0, 0, 0, 1, 1, 0, 1, 0]
[0, 0, 0, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 1]
[0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 1, 0, 1]
[0, 0, 1, 0, 0, 1, 1, 0]
[0, 0, 1, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 1]
[0, 0, 1, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 1, 0, 1, 1]
[0, 0, 1, 0, 1, 1, 0, 0]
[0, 0, 1, 0, 1, 1, 0, 1]
[0, 0, 1, 0, 1, 1, 1, 0]
[0, 0, 1, 0, 1, 1, 1, 1]
[0, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 1]
[0, 0, 1, 1, 0, 0, 1, 0]
[0, 0, 1, 1, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 1, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 1, 1, 0]
[0, 0, 1, 1, 0, 1, 1, 1]
[0, 0, 1, 1, 1, 0, 0, 0]
[0, 0, 1, 1, 1, 0, 0, 1]
[0, 0, 1, 1, 1, 0, 1, 0]
[0, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 1, 1, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 0]
[0, 0, 1, 1, 1, 1, 1, 1]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 1, 1]
[0, 1, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 1, 0, 1]
[0, 1, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 1, 1, 1]
[0, 1, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 0, 1]
[0, 1, 0, 0, 1, 0, 1, 0]
[0, 1, 0, 0, 1, 0, 1, 1]
[0, 1, 0, 0, 1, 1, 0, 0]
[0, 1, 0, 0, 1, 1, 0, 1]
[0, 1, 0, 0, 1, 1, 1, 0]
[0, 1, 0, 0, 1, 1, 1, 1]
[0, 1, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 1]
[0, 1, 0, 1, 0, 0, 1, 0]
[0, 1, 0, 1, 0, 0, 1, 1]
[0, 1, 0, 1, 0, 1, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 0, 1, 1, 0]
[0, 1, 0, 1, 0, 1, 1, 1]
[0, 1, 0, 1, 1, 0, 0, 0]
[0, 1, 0, 1, 1, 0, 0, 1]
[0, 1, 0, 1, 1, 0, 1, 0]
[0, 1, 0, 1, 1, 0, 1, 1]
[0, 1, 0, 1, 1, 1, 0, 0]
[0, 1, 0, 1, 1, 1, 0, 1]
[0, 1, 0, 1, 1, 1, 1, 0]
[0, 1, 0, 1, 1, 1, 1, 1]
[0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 1]
[0, 1, 1, 0, 0, 0, 1, 0]
[0, 1, 1, 0, 0, 0, 1, 1]
[0, 1, 1, 0, 0, 1, 0, 0]
[0, 1, 1, 0, 0, 1, 0, 1]
[0, 1, 1, 0, 0, 1, 1, 0]
[0, 1, 1, 0, 0, 1, 1, 1]
[0, 1, 1, 0, 1, 0, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 1]
[0, 1, 1, 0, 1, 0, 1, 0]
[0, 1, 1, 0, 1, 0, 1, 1]
[0, 1, 1, 0, 1, 1, 0, 0]
[0, 1, 1, 0, 1, 1, 0, 1]
[0, 1, 1, 0, 1, 1, 1, 0]
[0, 1, 1, 0, 1, 1, 1, 1]
[0, 1, 1, 1, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 1]
[0, 1, 1, 1, 0, 0, 1, 0]
[0, 1, 1, 1, 0, 0, 1, 1]
[0, 1, 1, 1, 0, 1, 0, 0]
[0, 1, 1, 1, 0, 1, 0, 1]
[0, 1, 1, 1, 0, 1, 1, 0]
[0, 1, 1, 1, 0, 1, 1, 1]
[0, 1, 1, 1, 1, 0, 0, 0]
[0, 1, 1, 1, 1, 0, 0, 1]
[0, 1, 1, 1, 1, 0, 1, 0]
[0, 1, 1, 1, 1, 0, 1, 1]
[0, 1, 1, 1, 1, 1, 0, 0]
[0, 1, 1, 1, 1, 1, 0, 1]
[0, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 0, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 1]
[1, 0, 0, 0, 0, 1, 1, 0]
[1, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 1, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 1, 0, 1, 1]
[1, 0, 0, 0, 1, 1, 0, 0]
[1, 0, 0, 0, 1, 1, 0, 1]
[1, 0, 0, 0, 1, 1, 1, 0]
[1, 0, 0, 0, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 1, 0, 0, 1, 0]
[1, 0, 0, 1, 0, 0, 1, 1]
[1, 0, 0, 1, 0, 1, 0, 0]
[1, 0, 0, 1, 0, 1, 0, 1]
[1, 0, 0, 1, 0, 1, 1, 0]
[1, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 1, 1, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 1, 0, 0]
[1, 0, 0, 1, 1, 1, 0, 1]
[1, 0, 0, 1, 1, 1, 1, 0]
[1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 0, 0, 1, 0]
[1, 0, 1, 0, 0, 0, 1, 1]
[1, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 0, 1, 0, 1]
[1, 0, 1, 0, 0, 1, 1, 0]
[1, 0, 1, 0, 0, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 0, 1]
[1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 0, 1, 1]
[1, 0, 1, 0, 1, 1, 0, 0]
[1, 0, 1, 0, 1, 1, 0, 1]
[1, 0, 1, 0, 1, 1, 1, 0]
[1, 0, 1, 0, 1, 1, 1, 1]
[1, 0, 1, 1, 0, 0, 0, 0]
[1, 0, 1, 1, 0, 0, 0, 1]
[1, 0, 1, 1, 0, 0, 1, 0]
[1, 0, 1, 1, 0, 0, 1, 1]
[1, 0, 1, 1, 0, 1, 0, 0]
[1, 0, 1, 1, 0, 1, 0, 1]
[1, 0, 1, 1, 0, 1, 1, 0]
[1, 0, 1, 1, 0, 1, 1, 1]
[1, 0, 1, 1, 1, 0, 0, 0]
[1, 0, 1, 1, 1, 0, 0, 1]
[1, 0, 1, 1, 1, 0, 1, 0]
[1, 0, 1, 1, 1, 0, 1, 1]
[1, 0, 1, 1, 1, 1, 0, 0]
[1, 0, 1, 1, 1, 1, 0, 1]
[1, 0, 1, 1, 1, 1, 1, 0]
[1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0, 1, 1]
[1, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 0, 0, 0, 1, 0, 1]
[1, 1, 0, 0, 0, 1, 1, 0]
[1, 1, 0, 0, 0, 1, 1, 1]
[1, 1, 0, 0, 1, 0, 0, 0]
[1, 1, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 1, 0, 1, 0]
[1, 1, 0, 0, 1, 0, 1, 1]
[1, 1, 0, 0, 1, 1, 0, 0]
[1, 1, 0, 0, 1, 1, 0, 1]
[1, 1, 0, 0, 1, 1, 1, 0]
[1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 0, 1, 0, 0, 0, 0]
[1, 1, 0, 1, 0, 0, 0, 1]
[1, 1, 0, 1, 0, 0, 1, 0]
[1, 1, 0, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 0, 1, 0, 0]
[1, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 0, 1, 0, 1, 1, 0]
[1, 1, 0, 1, 0, 1, 1, 1]
[1, 1, 0, 1, 1, 0, 0, 0]
[1, 1, 0, 1, 1, 0, 0, 1]
[1, 1, 0, 1, 1, 0, 1, 0]
[1, 1, 0, 1, 1, 0, 1, 1]
[1, 1, 0, 1, 1, 1, 0, 0]
[1, 1, 0, 1, 1, 1, 0, 1]
[1, 1, 0, 1, 1, 1, 1, 0]
[1, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 0, 0, 0, 1, 0]
[1, 1, 1, 0, 0, 0, 1, 1]
[1, 1, 1, 0, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 1, 0, 1]
[1, 1, 1, 0, 0, 1, 1, 0]
[1, 1, 1, 0, 0, 1, 1, 1]
[1, 1, 1, 0, 1, 0, 0, 0]
[1, 1, 1, 0, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 0, 1, 0]
[1, 1, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1, 0, 0]
[1, 1, 1, 0, 1, 1, 0, 1]
[1, 1, 1, 0, 1, 1, 1, 0]
[1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 1]
[1, 1, 1, 1, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 0, 1, 0, 0]
[1, 1, 1, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 0, 1, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 0]
[1, 1, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1, 1, 1]


И никаких тебе аномалий...

Автор: kolpeex1 12.3.2010, 05:22
Нормальное заполнение-то я сделал. Меня конкретно смущает то, что запись в элемент массива переписывает все элементы.

А алгоритм простой:
Внешний цикл - это обход столбцов.
density - это плотность заполнения, изначально равная половине количества вариантов.
Самый внутренний цикл заполняет density ячеек нулями, а потом (цикл values.each) единичками.
Для следующего ряда density уменьшается вдвое.
Примерно так:
Код

density = 4
0
0
0
0
1
1
1
1
density = 2
0
0
1
1
density = 1
0
1

Но поскольку каждый ряд заполнен только на density значений, я повторяю заполнение. При чём количество повторов удваивается каждый ряд
Код

density:
421
repeats:
124
bits:
000
001
010
011
100
101
110
111


А насчёт сопровождения: я специально вынес размерность и принимаемые аргументы. Чтобы в будущем просто использовать это код без изменений. Например, чтобы получить массив всех возможных IP-адресов, достаточно задать x_from=0, x_to=3, values=(0..255).to_a

Автор: source777 12.3.2010, 12:49
Цитата(kolpeex1 @  12.3.2010,  05:22 Найти цитируемый пост)
Нормальное заполнение-то я сделал.

Что ж в нём нормального, если даже ты как автор не можешь понять почему он не работает корректно, а на выходе получается массив из одних единиц. Код не просто попахивает, он воняет: взять хотя бы 4 вложенных цикла для заполнения двумерного массива, за такое можно смело премии лишать.  smile  А если серьёзно, то рефакторинг просто необходим, чтобы код стал нормальным и читаемым. 


Цитата(kolpeex1 @  12.3.2010,  05:22 Найти цитируемый пост)
Меня конкретно смущает то, что запись в элемент массива переписывает все элементы.

Чего ж тебя смущает, ты ведь сам под все вложенные массивы выделил одну общую область памяти:
Код

tests = Array.new variants, (Array.new ((x_to - x_from + 1), 0))

можно конечно просто продемонстрировать глубокое знание Ruby и использовать правильный для данного случая синтаксис:
Код

tests = Array.new(variants) { Array.new(x_to - x_from + 1, 0) }


Но лучше выкинуть все 24 строки и переписать нормально весь алгоритм, чтобы код стал читабельным, а не write-only. Всё-таки Ruby - очень выразительный язык, и весьма неприятно видеть подобные примеры его использования.

Автор: kolpeex1 14.3.2010, 17:33
Спасибо!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)