@kmskelton/

Dutch National Flag variations

Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# For speed testing at the bottom
import timeit

a = [0,1,2,0,2,1,1]

# Given an array and a pointer element, sort the values into less than, and greater than the pointer value. 

# This is the 'naive' solution provided by Elements in Programming Interviews in Python
def dnf(arr, pointer):
  pivot = arr[pointer]
  # group elements smaller than the pivot
  for i in range(len(arr)):
    # find the elements in the array that are smaller than the pivot
    for j in range(i+1, len(arr)):
      if arr[j] < pivot:
        arr[i], arr[j] = arr[j], arr[i]
        break
  # second pass to find values larger than the pivot
  for i in reversed(range(len(arr))):
    # the less than pivot values have been managed above
    if arr[i] < pivot:
      break 
    for j in reversed(range(i)):
      if arr[j] > pivot:
        arr[i], arr[j] = arr[j], arr[i]
        break
  return(arr)
print("basic", dnf(a, 3))

# This is the improved solution in EPIP
def imp_dnf(arr, pointer):
  pivot=a[pointer]
  smaller = 0
  # 1st pass group smaller
  for i in range(len(arr)):
    if arr[i] < pivot:
      arr[i], arr[smaller] = arr[smaller], arr[i]
      smaller += 1
  larger = len(arr) - 1
  for i in reversed(range(len(arr))):
    if arr[i] < pivot:
      break
    elif arr[i] > pivot:
      arr[i], arr[larger] = arr[larger], arr[i] 
      larger -= 1
  return(arr)
print("impv", imp_dnf(a, 3))

# EPIP's best solution:
def best_dnf(arr, pointer):
  pivot=arr[pointer]
  smaller = 0
  equal = 0
  larger = len(arr)
  # iterate so long as there is an unclassified element
  while equal < larger:
    if arr[equal] < pivot:
      arr[smaller], arr[equal] = arr[equal], arr[smaller]
      smaller += 1
      equal += 1
    elif arr[equal] == pivot:
      equal += 1
    else: # arr[equal] > pivot
      larger -= 1
      arr[equal], arr[larger] = arr[larger], arr[equal]
  return(arr)
print("best: ", best_dnf(a, 3))

# This was my whiteboard solution at a recent meetup
# it does require double the memory, but it's routinely 2x faster
def my_dnf(arr, pointer):
  pivot = arr[pointer]
  temp_arr = []
  for val in arr:
    if val < pivot:
      temp_arr.insert(0, val)
    else:
      temp_arr.append(val)
  return(temp_arr)
print("mine: ", my_dnf(a, 3))

print("\n\n\n")
print(dnf(a, 2))
print(imp_dnf(a, 2))
print(best_dnf(a, 2))
print(my_dnf(a, 2))
print("\n\n\n")
print(dnf(a, 5))
print(imp_dnf(a, 5))
print(best_dnf(a, 5))
print(my_dnf(a, 5))
print("\n\n\n")


print("Begin speed tests......(time in seconds)")

arr = [0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1,0,1,2,0,2,1,1]

print("original, 10 times: ", timeit.timeit(lambda:dnf(arr, 3), number=10))
print("improved, 10 times: ", timeit.timeit(lambda:imp_dnf(arr, 3), number=10))
print("best, 10 times: ", timeit.timeit(lambda:best_dnf(arr, 3), number=10))
print("My implementation, 10 times: ", timeit.timeit(lambda:my_dnf(arr, 3), number=10))
print("\n\n\n")
print("original, 100 times: ", timeit.timeit(lambda:dnf(arr, 3), number=100))
print("improved, 100 times: ", timeit.timeit(lambda:imp_dnf(arr, 3), number=100))
print("best, 100 times: ", timeit.timeit(lambda:best_dnf(arr, 3), number=100))
print("My implementation, 100 times: ", timeit.timeit(lambda:my_dnf(arr, 3), number=100))
print("\n\n\n")
print("original, 500 times: ", timeit.timeit(lambda:dnf(arr, 3), number=500))
print("improved, 500 times: ", timeit.timeit(lambda:imp_dnf(arr, 3), number=500))
print("best, 500 times: ", timeit.timeit(lambda:best_dnf(arr, 3), number=500))
print("My implementation, 500 times: ", timeit.timeit(lambda:my_dnf(arr, 3), number=500))


'''
The best implementation depends on the bottleneck in the system. 
If I have to do this on a RaspberryPi I'd probably try my implementation and see if there's still storage space; if not, let's implement best_dnf. Same if I'm doing this on a cloud computing platform because there's probably a storage limitation. If I'm in a browser I'd use my implementation because I'll use all of your system's resources all day
'''


'''
These "code golf" answers drive me nuts. Essentially you can't get to EPIP's answer unless you a) know it or b) have most of the standard library memorized. I hadn't seen a,b=b,a before, so I had to look it up:


https://stackoverflow.com/questions/21047524/how-does-swapping-of-members-in-the-python-tuples-a-b-b-a-work-internally
Python separates the right-hand side expression from the left-hand side assignment. First the right-hand side is evaluated, and the result is stored on the stack, and then the left-hand side names are assigned using opcodes that take values from the stack again.
'''