Почему Ruby Array # count ненадежен для больших массивов?

Question

Я перебираю комбинацию из 2 элементов довольно большого массива.При подсчете элементов комбинации я обнаружил нечто странное.В следующем примере показано, что я имею в виду:

[1] pry(main)> 10000.times.to_a.combination(2).count
=> 49995000   # correct

[2] pry(main)> 100000.times.to_a.combination(2).count
=> 704982704  # wrong, should be 4999950000

[3] pry(main)> count = 0; 100000.times.to_a.combination(2).each { count+=1 }; count
=> 4999950000 # correct

Я дважды проверил результаты, используя wolframalpha:

• пары из 10000 записей https://www.wolframalpha.com/input/?i=10000!%2F((10000-2)!*2!)
• пары из100000 записей https://www.wolframalpha.com/input/?i=100000!%2F((100000-2)!*2!)

Мой вопрос на самом деле, почему Array#count не является надежным в этом случае?

Также см. https://ruby -doc.org / core-2.2.0 / Array.html # method-i-комбинация и https://ruby -doc.org / core-2.2.0 / Array.html # method-i-count .

Большое спасибо.

Answer 1

Array#count не является ошибочным методом, Enumerator#count - это:

100000.times.to_a.combination(2).class # => Enumerator

Хорошая новость заключается в том, что ошибка, с которой вы столкнулись, была зарегистрирована несколько месяцев назад как # 14805 и впоследствии исправлено, но плохие новости с тех пор не было выпущено никакой новой версии CRuby.Так что либо дождитесь 2.5.2, 2.4.5 и т. Д., Либо скомпилируйте версию с исправлением самостоятельно.

Проблема в том, что счетчик перечислителя ограничен 32-разрядным целым числом со знаком, поэтомупроизошло переполнение:

max = (1 << 31) - 1 # max value
4999950000 & max    # => 704982704

Это было исправлено путем создания счетчика bignum (целочисленный тип произвольной точности Ruby, так как 2.4 - внутренняя деталь реализации) в случае, если его значение выходит за пределы int илина данный момент unsigned long.