модифицированный алгоритм 3SUM не очень хорошо работает с плавающей точкой

Question

Так я пытаюсь решить проблему 3SUM и следующего моего алгоритм

def findThree(seq, goal): 
    for x in range(len(seq)-1): 

     left = x+1 
     right = len(seq)-1 

     while (left < right): 
      tmp = seq[left] + seq[right] + seq[x] 
      if tmp > goal: 
       right -= 1 
      elif tmp < goal: 
       left += 1 
      else: 
       return [seq[left],seq[right],seq[x]] 

Как вы можете видеть, что это действительно универсальный алгоритм, который решает эту проблему в O (n).

Проблема, с которой я столкнулся, заключается в том, что этот алгоритм не похож на работу с числами с плавающей запятой.

Чтобы проверить, что моя теория верна, я дал ему следующие два массива

FloatingArr = [89.95, 120.0, 140.0, 179.95, 199.95, 259.95, 259.95, 259.95, 320.0, 320.0] 
IntArr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320] 


findThree(FloatingArr, 779.85) // I want it to return [259.95, 259.95, 259,95] 
>> None // Fail 
findThree(FloatingArr, 777) // I want it to return [259,259,259] 
>> [259, 259, 259] // Success 

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

Для получения дополнительной информации, мой первый массив изначально представляет собой список строк цен, но для того, чтобы сделать математику с ними, мне пришлось снять знак «$». Мой подход при этом заключается в том, что это

for x in range(len(prices)): 
    prices[x] = float(prices[x][1:]) // return all the prices without the "$" sign. Casting them to float. 

Если есть намного лучший способ, пожалуйста, дайте мне знать. Я чувствую, что эта проблема не совсем о findThree(), а скорее как я изменил исходный массив цен.

Редактировать: Увидеть, что это действительно проблема с плавающей точкой, я думаю, мой следующий вопрос будет лучшим способом преобразования строки в int после того, как я отключу «$»?

Answer 1

Это не работает, потому что числа, подобные 89.95, как правило, не могут быть сохранены точно (поскольку представление base-two из 0.95 является повторяющимся десятичным).

В целом, имея дело с числами с плавающей запятой, вместо сравнения для точного равенства через ==, вы хотите проверить, достаточно ли чисел «достаточно близко», чтобы считаться равными; обычно делается с abs(a - b) < SOME_THRESHOLD. Точное значение SOME_THRESHOLD зависит от того, насколько вы точны быть точным, и, как правило, требует проб и ошибок, чтобы получить хорошее значение.

В вашем конкретном случае, потому что вы работаете с долларами и центами, вы можете просто конвертировать в центы путем умножения на 100 и округление до целого числа (через round, потому что int завершат т.е. 7.999999 до 7). Тогда ваш набор чисел будет просто целым числом, решая проблему округления.

Answer 2

Вы можете преобразовать свои цены из строки в целые числа, а не конвертировать их в поплавки. Предположим, что все цены имеют не более k цифр после десятичной точки (в исходном представлении строки). Тогда 10^k * price всегда целое число. Таким образом, вы полностью можете избавиться от вычислений с плавающей запятой.

Пример: если после запятой есть не более двух цифр, $2.10 становится 210 и $2.2 становится 220. Нет необходимости использовать float даже в промежуточных вычислениях, потому что вы можете сдвинуть десятичную точку на две позиции вправо (при необходимости добавить нули), а затем преобразовать строку непосредственно в целое число.

Ниже приведен пример функции конвертирования:

def convert(price, max_digits): 
    """ price - a string representation of the price 
     max_digits - maximum number of digits after a decimal point 
        among all prices 
    """ 
    parts = price[1:].split('.') 
    if len(parts) == 2 and len(parts[1]) > 0: 
     return int(parts[0]) * 10 ** max_digits + \ 
       int(parts[1]) * 10 ** (max_digits - len(parts[1])) 
    else: 
     return int(parts[0]) * 10 ** max_digits