Нахождение ближайшего числа к целевой сумме списка

Ловить NullPointerException - действительно проблематичная вещь, потому что они могут случиться почти где угодно. Очень легко получить один из ошибок, поймать его случайно и продолжить, как будто все нормально, что скрывает настоящую проблему. Сложно справиться с этим, поэтому лучше всего избегать. (Например, подумайте об авто-распаковке нулевого Integer.)

Вместо этого я рекомендую вам использовать класс Optional . Это часто лучший подход, когда вы хотите работать со значениями, которые присутствуют или отсутствуют.

Используя это, вы можете написать свой код следующим образом:

public Optional m(Ws wsObject) {
    return Optional.ofNullable(wsObject.getFoo()) // Here you get Optional.empty() if the Foo is null
        .map(f -> f.getBar()) // Here you transform the optional or get empty if the Bar is null
        .map(b -> b.getBaz())
        .map(b -> b.getInt());
        // Add this if you want to return an -1 int instead of an empty optional if any is null
        // .orElse(-1);
        // Or this if you want to throw an exception instead
        // .orElseThrow(SomeApplicationException::new);
}

Почему необязательно?

Использование Optional s вместо null для значений, которые могут отсутствовать, делает этот факт очень понятным и понятным для читателей, а система типов гарантирует, что вы не случайно забыли о это.

Вы также получаете доступ к методам работы с такими значениями более удобно, например map и orElse .


Является ли отсутствие действительным или ошибкой?

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


Возможно, больше опций?

Если, с другой стороны, отсутствующие значения из промежуточных методов действительны, возможно, вы также можете переключиться на Optional s для них?

Тогда вы могли бы использовать их следующим образом:

public Optional mo(Ws wsObject) {
    return wsObject.getFoo()
        .flatMap(f -> f.getBar())
        .flatMap(b -> b.getBaz())
        .flatMap(b -> b.getInt());        
}

Почему не факультативно?

Единственная причина, по которой я могу думать, f11], если это действительно критически важная часть кода, и если накладные расходы на сбор мусора оказываются проблемой. Это связано с тем, что при каждом запуске кода выделяется несколько объектов Optional, и VM может не быть в состоянии оптимизировать их. В этом случае ваши оригинальные if-тесты могут быть лучше.

0
задан Macterror 30 March 2019 в 22:33
поделиться

2 ответа

Вы можете использовать min(), чтобы получить последовательность, которая имеет наименьшую абсолютную разницу между суммой и целью, например, используя параметр key для min():

import itertools as it

# From itertools recipes
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(len(s)+1))

In []:
target = 2842.77
result = min(powerset(numbers), key=lambda seq: abs(sum(seq)-target))
result

Out[]:
(2505.71, 337.86)

In []:
sum(result)

Out[]:
2843.57
0
ответ дан AChampion 30 March 2019 в 22:33
поделиться

Ваше решение с использованием комбинаций хорошо, если ваш список небольшой, но учтите, что сумма combinations(number, i) по всем i равна 2**len(numbers). Это очень быстро растет и убьет вашу программу.

Ваша проблема известна как «Подмножество сумм», где вы хотите выбрать подмножество чисел для суммирования с вашей суммой. Он очень хорошо известен и имеет очень много вариантов и решений. Он также является NP-полным, то есть для него не существует реального полиномиального (быстрого) решения.

Тем не менее, существует псевдополиномиальное решение с использованием динамического программирования.

Пример здесь: https://www.geeksforgeeks.org/subset-sum-problem-dp-25/

0
ответ дан Christian Sloper 30 March 2019 в 22:33
поделиться
Другие вопросы по тегам:

Похожие вопросы: