Skip to content

Instantly share code, notes, and snippets.

@surt91
Last active August 29, 2015 14:02
Show Gist options
  • Save surt91/e399500e780e184d9ac7 to your computer and use it in GitHub Desktop.
Save surt91/e399500e780e184d9ac7 to your computer and use it in GitHub Desktop.
Generates an approximation of a sorted list of integers using Simulated Annealing. Faster than Bogosort in many cases!
#!/usr/bin/env python3
from random import random, randint, sample
from math import exp
from copy import deepcopy
from time import time
class SimulatedSort():
def __init__(self):
self.T = [300.0, 100.0, 70.0, 30.0, 10.0, 7.0, 3.0, 1.0]
self.t_steps = 100
def __call__(self, to_sort):
self.conf = Configuration(to_sort)
self.simulated_annealing()
return self.conf.conf
def simulated_annealing(self):
new_conf = self.conf
best_conf = deepcopy(self.conf)
for t in self.T:
for i in range(self.t_steps):
old_f = new_conf.f
new_conf.change()
if new_conf.f < old_f or random() < exp(-(new_conf.f - old_f) / t):
if new_conf.f < best_conf.f:
best_conf = deepcopy(new_conf)
else:
new_conf.revert_last_change()
print(t, self.conf.conf, self.conf.f)
class Configuration():
def __init__(self, conf):
self.conf = conf
self.update_penalty()
def update_penalty(self):
p = 0
for i in range(len(self.conf) - 1):
p += abs(self.conf[i] - self.conf[i + 1])
self.f = p
def change(self):
self.x = randint(0, len(self.conf) - 1)
self.y = randint(0, len(self.conf) - 1)
self.conf[self.x], self.conf[self.y] = self.conf[self.y], self.conf[self.x]
self.update_penalty()
def revert_last_change(self):
self.conf[self.x], self.conf[self.y] = self.conf[self.y], self.conf[self.x]
self.update_penalty()
if __name__ == "__main__":
l = sample(range(0, 1000), 10)
print(l)
a = SimulatedSort()
start = time()
s = a(l)
end = time()
sa_time = end-start
print("finished after {:.3f}s".format(sa_time))
print(s)
if all(s[i] <= s[i+1] for i in range(len(s)-1))
or all(s[i] >= s[i+1] for i in range(len(s)-1)):
print("list is sorted!")
else:
print("not sorted!")
start = time()
s = sorted(l)
end = time()
tim_time = end-start
print("timsort would have needed: "
"{:.8f}s ({:.0f} times faster)".format(tim_time, sa_time/tim_time))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment