import itertools
import math
import operator
from collections import Counter
from timeit import timeit
from typing import Callable, Any
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def r_functional(arr: list[int]) -> bool:
arr.sort()
return all(
itertools.starmap(operator.eq, enumerate(arr))
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
def ahall_a(arr: list[int]) -> bool:
return False if len(arr) == 0 else set(arr) == set(range(len(arr)))
def ahall_b(arr: list[int]) -> bool:
return bool(arr) and set(arr) == set(range(len(arr)))
def ahall_c(arr: list[int]) -> bool:
return set(arr) == set(range(len(arr) or 1))
def sudix_b(arr: list[int]) -> bool:
bit_arr = np.zeros(len(arr),dtype=bool)
for x in arr:
if x<0 or x>= len(arr):
return False
if bit_arr[x] == True:
return False
bit_arr[x] = True
return True
METHODS = (
op,
jh_a,
# jh_b, # fails for [0 0 3 3]
jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum, r_functional,
ahall_a, ahall_b, ahall_c,
# sudix_a, # fails for [0]
sudix_b,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(0, 0, 3, 3), # This disqualifies jh_b
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True, f'{method.__name__} failed example'
for example in counterexamples:
assert not method(list(example)) is False, f'{method.__name__} failed counterexample'
def benchmark() -> None:
rand = default_rng(seed=0)
def make_shuffle(n: int) -> np.ndarray:
series = np.arange(n)
rand.shuffle(series)
return series
rows = []
kinds = (
('repeated_0', lambda n: np.full(shape=n, fill_value=0)),
('repeated_hi', lambda n: np.full(shape=n, fill_value=n + 1)),
('sorted', lambda n: np.arange(n)),
('shuffled', make_shuffle),
)
for kind, make_input in kinds:
sizes = (10**np.linspace(0, 4, num=6)).astype(int)
def run_all(
rep: int,
n: int,
inputs: np.ndarray,
methods: tuple[Callable, ...],
) -> list[dict[str, Any]]:
result = []
for method in methods:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
result.append({
'n': n,
'kind': kind,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
return result
prune_rows = run_all(rep=0, n=sizes[-1], inputs=make_input(sizes[-1]), methods=METHODS)
prune_rows.sort(key=lambda row: row['dur'])
pruned_methods = [
next(
method
for method in METHODS
if method.__name__ == row['method']
)
for row in prune_rows[:len(prune_rows)//2][::-1]
]
for n in sizes:
inputs = make_input(n)
for rep in range(5):
rows.extend(run_all(rep=rep, n=n, inputs=inputs, methods=pruned_methods))
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
fig.suptitle(f'{len(METHODS)//2} fastest methods, four input kinds')
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()
The above functional approach may be your best choice as an all-around efficient implementation.
To summarise thisthe input-kind effect over all of the methods we've seen so far:
import itertools
import math
import operator
from collections import Counter
from timeit import timeit
from typing import Callable, Any
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def r_functional(arr: list[int]) -> bool:
arr.sort()
return all(
itertools.starmap(operator.eq, enumerate(arr))
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
def ahall_a(arr: list[int]) -> bool:
return False if len(arr) == 0 else set(arr) == set(range(len(arr)))
def ahall_b(arr: list[int]) -> bool:
return bool(arr) and set(arr) == set(range(len(arr)))
def ahall_c(arr: list[int]) -> bool:
return set(arr) == set(range(len(arr) or 1))
def sudix_b(arr: list[int]) -> bool:
bit_arr = np.zeros(len(arr),dtype=bool)
for x in arr:
if x<0 or x>= len(arr):
return False
if bit_arr[x] == True:
return False
bit_arr[x] = True
return True
METHODS = (
op,
jh_a,
# jh_b, # fails for [0 0 3 3]
jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum, r_functional,
ahall_a, ahall_b, ahall_c,
# sudix_a, # fails for [0]
sudix_b,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(0, 0, 3, 3), # This disqualifies jh_b
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True, f'{method.__name__} failed example'
for example in counterexamples:
assert method(list(example)) is False, f'{method.__name__} failed counterexample'
def benchmark() -> None:
rand = default_rng(seed=0)
def make_shuffle(n: int) -> np.ndarray:
series = np.arange(n)
rand.shuffle(series)
return series
rows = []
for nkinds in= (10**np.linspace
(0'repeated_0', 4,lambda num=6))n: np.astypefull(intshape=n, fill_value=0):),
pre_sorted('repeated_hi', =lambda n: np.arangefull(nshape=n, fill_value=n + 1)),
shuffled('sorted', =lambda pre_sortedn: np.copyarange(n)),
rand.shuffle(shuffled'shuffled', make_shuffle),
)
kindsfor =kind, (
make_input in kinds:
sizes = ('sorted'10**np.linspace(0, pre_sorted)4, num=6)).astype(int)
def run_all(
('shuffled', shuffled) rep: int,
('repeated_0', np.full_like(pre_sorted,n: fill_value=0))int,
('repeated_hi',inputs: np.full_like(pre_sorted, fill_value=n + 1))ndarray,
)
methods: tuple[Callable, ...],
for rep in range(5):
) -> list[dict[str, Any]]:
for kind_name, inputs in kinds:
result = []
for method in METHODSmethods:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
rowsresult.append({
'n': n,
'kind': kind_namekind,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
}) return result
prune_rows = run_all(rep=0, n=sizes[-1], inputs=make_input(sizes[-1]), methods=METHODS)
prune_rows.sort(key=lambda row: row['dur'])
pruned_methods = [
next(
method
for method in METHODS
if method.__name__ == row['method']
)
for row in prune_rows[:len(prune_rows)//2][::-1]
]
for n in sizes:
inputs = make_input(n)
for rep in range(5):
rows.extend(run_all(rep=rep, n=n, inputs=inputs, methods=pruned_methods))
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
fig.suptitle(f'{len(METHODS)//2} fastest methods, four input kinds')
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()
To summarise this effect over all of the methods we've seen so far:
import itertools
import math
import operator
from collections import Counter
from timeit import timeit
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def r_functional(arr: list[int]) -> bool:
arr.sort()
return all(
itertools.starmap(operator.eq, enumerate(arr))
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
METHODS = (
op,
jh_a, # jh_b,
jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum, r_functional,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(0, 0, 3, 3), # This disqualifies jh_b
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True
for example in counterexamples:
assert method(list(example)) is False
def benchmark() -> None:
rand = default_rng(seed=0)
rows = []
for n in (10**np.linspace(0, 4, num=6)).astype(int):
pre_sorted = np.arange(n)
shuffled = pre_sorted.copy()
rand.shuffle(shuffled)
kinds = (
('sorted', pre_sorted),
('shuffled', shuffled),
('repeated_0', np.full_like(pre_sorted, fill_value=0)),
('repeated_hi', np.full_like(pre_sorted, fill_value=n + 1)),
)
for rep in range(5):
for kind_name, inputs in kinds:
for method in METHODS:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
rows.append({
'n': n,
'kind': kind_name,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()
The above functional approach may be your best choice as an all-around efficient implementation.
To summarise the input-kind effect over all of the methods we've seen so far:
import itertools
import math
import operator
from collections import Counter
from timeit import timeit
from typing import Callable, Any
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def r_functional(arr: list[int]) -> bool:
arr.sort()
return all(
itertools.starmap(operator.eq, enumerate(arr))
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
def ahall_a(arr: list[int]) -> bool:
return False if len(arr) == 0 else set(arr) == set(range(len(arr)))
def ahall_b(arr: list[int]) -> bool:
return bool(arr) and set(arr) == set(range(len(arr)))
def ahall_c(arr: list[int]) -> bool:
return set(arr) == set(range(len(arr) or 1))
def sudix_b(arr: list[int]) -> bool:
bit_arr = np.zeros(len(arr),dtype=bool)
for x in arr:
if x<0 or x>= len(arr):
return False
if bit_arr[x] == True:
return False
bit_arr[x] = True
return True
METHODS = (
op,
jh_a,
# jh_b, # fails for [0 0 3 3]
jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum, r_functional,
ahall_a, ahall_b, ahall_c,
# sudix_a, # fails for [0]
sudix_b,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(0, 0, 3, 3), # This disqualifies jh_b
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True, f'{method.__name__} failed example'
for example in counterexamples:
assert method(list(example)) is False, f'{method.__name__} failed counterexample'
def benchmark() -> None:
rand = default_rng(seed=0)
def make_shuffle(n: int) -> np.ndarray:
series = np.arange(n)
rand.shuffle(series)
return series
rows = []
kinds = (
('repeated_0', lambda n: np.full(shape=n, fill_value=0)),
('repeated_hi', lambda n: np.full(shape=n, fill_value=n + 1)),
('sorted', lambda n: np.arange(n)),
('shuffled', make_shuffle),
)
for kind, make_input in kinds:
sizes = (10**np.linspace(0, 4, num=6)).astype(int)
def run_all(
rep: int,
n: int,
inputs: np.ndarray,
methods: tuple[Callable, ...],
) -> list[dict[str, Any]]:
result = []
for method in methods:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
result.append({
'n': n,
'kind': kind,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
return result
prune_rows = run_all(rep=0, n=sizes[-1], inputs=make_input(sizes[-1]), methods=METHODS)
prune_rows.sort(key=lambda row: row['dur'])
pruned_methods = [
next(
method
for method in METHODS
if method.__name__ == row['method']
)
for row in prune_rows[:len(prune_rows)//2][::-1]
]
for n in sizes:
inputs = make_input(n)
for rep in range(5):
rows.extend(run_all(rep=rep, n=n, inputs=inputs, methods=pruned_methods))
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
fig.suptitle(f'{len(METHODS)//2} fastest methods, four input kinds')
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()
Add unit tests.
import itertools
import math
import operator
from collections import Counter
from timeit import timeit
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_b(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def r_functional(arr: list[int]) -> bool:
arr.sort()
return all(
itertools.starmap(operator.eq, enumerate(arr))
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
METHODS = (
op,
jh_a, # jh_b,
jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum, r_functional,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(0, 0, 3, 3), # This disqualifies jh_b
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True
for example in counterexamples:
assert method(list(example)) is False
def benchmark() -> None:
rand = default_rng(seed=0)
rows = []
for n in (10**np.linspace(0, 4, num=6)).astype(int):
pre_sorted = np.arange(n)
shuffled = pre_sorted.copy()
rand.shuffle(shuffled)
kinds = (
('sorted', pre_sorted),
('shuffled', shuffled),
('repeated_0', np.full_like(pre_sorted, fill_value=0)),
('repeated_hi', np.full_like(pre_sorted, fill_value=n + 1)),
)
for rep in range(5):
for kind_name, inputs in kinds:
for method in METHODS:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
rows.append({
'n': n,
'kind': kind_name,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()
import math
from collections import Counter
from timeit import timeit
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_b(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
METHODS = (
op,
jh_a, jh_b, jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True
for example in counterexamples:
assert method(list(example)) is False
def benchmark() -> None:
rand = default_rng(seed=0)
rows = []
for n in (10**np.linspace(0, 4, num=6)).astype(int):
pre_sorted = np.arange(n)
shuffled = pre_sorted.copy()
rand.shuffle(shuffled)
kinds = (
('sorted', pre_sorted),
('shuffled', shuffled),
('repeated_0', np.full_like(pre_sorted, fill_value=0)),
('repeated_hi', np.full_like(pre_sorted, fill_value=n + 1)),
)
for rep in range(5):
for kind_name, inputs in kinds:
for method in METHODS:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
rows.append({
'n': n,
'kind': kind_name,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()
Add unit tests.
import itertools
import math
import operator
from collections import Counter
from timeit import timeit
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng
def op(arr):
if len(arr) == 0:
return False
n = len(arr) - 1
i = 0
for x in sorted(arr):
if x != i:
return False
i += 1
return True
def jh_a(arr: list[int]) -> bool:
arr.sort()
return (
len(set(arr)) == len(arr)
and arr[0] == 0
and arr[-1] == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def jh_c(arr: list[int]) -> bool:
n = len(arr)
expected_sum = n * (n - 1) / 2
return (
math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
and sum(arr) == expected_sum
and min(arr) == 0
and max(arr) == len(arr) - 1
and all(isinstance(x, int) for x in arr)
)
def factorial(n: int) -> int:
return math.prod(range(1, n + 1))
def jh_d(arr: list[int]) -> bool:
arr.sort()
return all(arr[i] == i for i in range(len(arr)))
def jh_e(arr: list[int]) -> bool:
arr.sort()
return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))
def r_enum(arr: list[int]) -> bool:
arr.sort()
return all(
i == x
for i, x in enumerate(arr)
)
def r_functional(arr: list[int]) -> bool:
arr.sort()
return all(
itertools.starmap(operator.eq, enumerate(arr))
)
def harith_a(arr: list[int]) -> bool:
if len(arr) == 0:
return False
for i, x in enumerate(sorted(arr)):
if x != i:
return False
return True
def harith_b(arr: list[int]) -> bool:
return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))
def harith_c(arr: list[int]) -> bool:
return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))
METHODS = (
op,
jh_a, # jh_b,
jh_c, jh_d, jh_e,
harith_a, harith_b, harith_c,
r_enum, r_functional,
)
def test() -> None:
examples = (
# (), # arguably appropriate here, but OP coded the opposite
(0,),
(1, 0, 2),
(2, 1, 0),
(0, 1, 2, 3, 4),
)
counterexamples = (
(1,),
(2, 1),
(1, 2, 3),
(0, 0, 3, 3), # This disqualifies jh_b
(-1, 0, 1, 2),
)
for method in METHODS:
for example in examples:
assert method(list(example)) is True
for example in counterexamples:
assert method(list(example)) is False
def benchmark() -> None:
rand = default_rng(seed=0)
rows = []
for n in (10**np.linspace(0, 4, num=6)).astype(int):
pre_sorted = np.arange(n)
shuffled = pre_sorted.copy()
rand.shuffle(shuffled)
kinds = (
('sorted', pre_sorted),
('shuffled', shuffled),
('repeated_0', np.full_like(pre_sorted, fill_value=0)),
('repeated_hi', np.full_like(pre_sorted, fill_value=n + 1)),
)
for rep in range(5):
for kind_name, inputs in kinds:
for method in METHODS:
inputs_list = inputs.tolist()
def run() -> bool:
return method(inputs_list)
rows.append({
'n': n,
'kind': kind_name,
'method': method.__name__,
'rep': rep,
'dur': timeit(stmt=run, number=1),
})
df = pd.DataFrame.from_dict(rows)
df = df.groupby(['n', 'kind', 'method'])['dur'].min()
fig, axes = plt.subplots(nrows=2, ncols=2)
axes = [ax for row in axes for ax in row]
for kind, ax in zip(df.index.unique('kind'), axes):
ax: Axes
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_title(kind)
sns.lineplot(
ax=ax,
data=df[(slice(None), kind, slice(None))].reset_index(),
x='n', y='dur', hue='method',
)
plt.show()
if __name__ == '__main__':
test()
benchmark()