[Python] Why the performance is bad if I use HashMap to solve Codility problem MinAbsSum?

Regarding the Codility problem MinAbsSum at https://app.codility.com/programmers/lessons/17-dynamic_programming/min_abs_sum/, the performance is bad if I use HashMap to solve the problem. I expect the performance to be similar to Array. I prefer to use HashMap because Array wastes a lot of memory if the number range is too large. Any idea why the HashMap is much slower than the Array?

import java.util.*;

public class MinAbsSumUsingHashMap {
// Total score = 54%
// Detected time complexity: O(N**2 * max(abs(A)))
public int solution(int[] A) {
// 1. Convert all numbers to absolute numbers
// 2. Sum all the converted absolute numbers
// 3. Count the occurrence of all the converted absolute numbers
int sum = 0;
Map<Integer, Integer> numberCountMap = new TreeMap<>();
for (int num : A) {
int absNum = Math.abs(num);
sum += absNum;
numberCountMap.merge(absNum, 1, Integer::sum);
}

AllPossibleSumNumbers allPossibleSumNumbers = new AllPossibleSumNumbers(sum);
for (Map.Entry<Integer, Integer> entry : numberCountMap.entrySet()) {
int absNum = entry.getKey();
int count = entry.getValue();
allPossibleSumNumbers.addPossibleSumNumber(absNum, count);
}

float halfSum = sum / 2f;
int halfSumFloor = (int) Math.floor(halfSum);
for (int bestPossibleHalfSum = halfSumFloor; bestPossibleHalfSum >= 0; bestPossibleHalfSum--) {
if (allPossibleSumNumbers.isPossibleSumNumber(bestPossibleHalfSum)) {
float halfDifference = halfSum - bestPossibleHalfSum;
float fullDifference = halfDifference * 2;
return (int) fullDifference;
}
}
return -1; // Ideally, it will not return -1.
}

class AllPossibleSumNumbers {
private final Map<Integer, Integer> allPossibleSumCounts = new HashMap<>();
private final int expectedSum;

public AllPossibleSumNumbers(int expectedSum) {
this.expectedSum = expectedSum;

// Sum 0 can be achieved without any number
int possibleSumNumber = 0;
int count = 0;
allPossibleSumCounts.put(possibleSumNumber, count);
}

public void addPossibleSumNumber(int num, int count) {
for (int possibleSum = 0; possibleSum <= expectedSum; possibleSum++) {
if (isPossibleSumNumber(possibleSum)) {
// we can set like this because no value num is needed to obtain the possibleSum
allPossibleSumCounts.put(possibleSum, count);
} else if (possibleSum >= num) {
// It is not a possible sum number, check the previous one
int prevPossibleSum = possibleSum - num;
Integer prevCount = allPossibleSumCounts.get(prevPossibleSum);
if (prevCount != null) {
// previous one is a possible sum number
int currCount = prevCount - 1; // currCount should be reduced by 1 because the num has been used once to achieve the current sum
if (currCount >= 0) {
// Is currCount >= 0 necessary? Got the same score after adding currCount >= 0 condition
allPossibleSumCounts.put(possibleSum, currCount);
}
}
}
}
}

public boolean isPossibleSumNumber(int num) {
Integer count = allPossibleSumCounts.get(num);
if (count == null) {
return false;
} else {
return count >= 0;
}
}
}
}


A similar code uses array can achieve a 100% score.

import java.util.*;

public class MinAbsSumUsingArray {
// Total score = 100%
// Detected time complexity: O(N * max(abs(A))**2)
public int solution(int[] A) {
// 1. Convert all numbers to absolute numbers
// 2. Sum all the converted absolute numbers
// 3. Count the occurrence of all the converted absolute numbers
int sum = 0;
Map<Integer, Integer> numberCountMap = new TreeMap<>();
for (int num : A) {
int absNum = Math.abs(num);
sum += absNum;
numberCountMap.merge(absNum, 1, Integer::sum);
}

AllPossibleSumNumbers allPossibleSumNumbers = new AllPossibleSumNumbers(sum);
for (Map.Entry<Integer, Integer> entry : numberCountMap.entrySet()) {
int absNum = entry.getKey();
int count = entry.getValue();
allPossibleSumNumbers.addPossibleSumNumber(absNum, count);
}

float halfSum = sum / 2f;
int halfSumFloor = (int) Math.floor(halfSum);
for (int bestPossibleHalfSum = halfSumFloor; bestPossibleHalfSum >= 0; bestPossibleHalfSum--) {
if (allPossibleSumNumbers.isPossibleSumNumber(bestPossibleHalfSum)) {
float halfDifference = halfSum - bestPossibleHalfSum;
float fullDifference = halfDifference * 2;
return (int) fullDifference;
}
}
return -1; // Ideally, it will not return -1.
}

class AllPossibleSumNumbers {
private final int[] allPossibleSumCounts;

public AllPossibleSumNumbers(int expectedSum) {
allPossibleSumCounts = new int[expectedSum + 1];

// first one is 0. the rest are -1
for (int i = 1; i < allPossibleSumCounts.length; i++) {
allPossibleSumCounts = -1;
}
}

public void addPossibleSumNumber(int num, int count) {
for (int possibleSum = 0; possibleSum < allPossibleSumCounts.length; possibleSum++) {
if (isPossibleSumNumber(possibleSum)) {
// we can set like this because no value num is needed to obtain the possibleSum
allPossibleSumCounts[possibleSum] = count;
} else if (possibleSum >= num) {
// It is not a possible sum number, check the previous one
int prevPossibleSum = possibleSum - num;
int prevCount = allPossibleSumCounts[prevPossibleSum];
int currCount = prevCount - 1; // currCount should be reduced by 1 because the num has been used once to achieve the current sum
allPossibleSumCounts[possibleSum] = currCount;
}
}
}

public boolean isPossibleSumNumber(int num) {
return allPossibleSumCounts[num] >= 0;
}
}
}


Interestingly, I just tried the same in Python, and both work fine. I assume the Python dictionary is equivalent to the Java HashMap. Please let me know if I am wrong.

def solution(A):
array_length = len(A)
# 1. Convert all numbers to absolute numbers
for best_possible_half_sum in range(array_length):
A[best_possible_half_sum] = abs(A[best_possible_half_sum])
# 2. Sum all the converted absolute numbers
abs_sum = sum(A)
# 3. Count the occurrence of all the converted absolute numbers
num_counts = {}
for num in A:
if num in num_counts:
num_counts[num] += 1
else:
num_counts[num] = 1

# Sum 0 can be achieved without any number
all_possible_sum_counts = {0: 0}

for num, count in num_counts.items():
for possible_sum in range(abs_sum):
if possible_sum in all_possible_sum_counts and all_possible_sum_counts[possible_sum] >= 0:
# we can set like this because no value num is needed to obtain the possible_sum
all_possible_sum_counts[possible_sum] = count
elif (possible_sum >= num):
# It is not a possible sum number, check the previous one
prev_possible_sum = possible_sum - num
if prev_possible_sum in all_possible_sum_counts:
# previous one is a possible sum number
prev_count = all_possible_sum_counts[prev_possible_sum]
curr_count = prev_count - 1 # currCount should be reduced by 1 because the num has been used once to achieve the current sum
all_possible_sum_counts[possible_sum] = curr_count

half_sum = abs_sum / 2
half_sum_floor = abs_sum // 2
for best_possible_half_sum in range(half_sum_floor, -1, -1):
if best_possible_half_sum in all_possible_sum_counts and all_possible_sum_counts[best_possible_half_sum] >= 0:
half_difference = half_sum - best_possible_half_sum
full_difference = half_difference * 2
return int(full_difference)


Below is the array version

def solution(A):
array_length = len(A)
# 1. Convert all numbers to absolute numbers
for best_possible_half_sum in range(array_length):
A[best_possible_half_sum] = abs(A[best_possible_half_sum])
# 2. Sum all the converted absolute numbers
abs_sum = sum(A)
# 3. Count the occurrence of all the converted absolute numbers
num_counts = {}
for num in A:
if num in num_counts:
num_counts[num] += 1
else:
num_counts[num] = 1

# first one is 0. the rest are -1
all_possible_sum_counts = [-1] * (abs_sum + 1)
all_possible_sum_counts[0] = 0

for num, count in num_counts.items():
for possible_sum in range(abs_sum):
if all_possible_sum_counts[possible_sum] >= 0:
# we can set like this because no value num is needed to obtain the possible_sum
all_possible_sum_counts[possible_sum] = count
elif (possible_sum >= num):
# It is not a possible sum number, check the previous one
prev_possible_sum = possible_sum - num
prev_count = all_possible_sum_counts[prev_possible_sum]
curr_count = prev_count - 1 # currCount should be reduced by 1 because the num has been used once to achieve the current sum
all_possible_sum_counts[possible_sum] = curr_count

half_sum = abs_sum / 2
half_sum_floor = abs_sum // 2
for best_possible_half_sum in range(half_sum_floor, -1, -1):
if all_possible_sum_counts[best_possible_half_sum] >= 0:
half_difference = half_sum - best_possible_half_sum
full_difference = half_difference * 2
return int(full_difference)

Continue reading...