I made an algorithm for my science fair project, and since I was mainly just interested in verifying its correctness (10000 correct answers speaks louder than a formal proof when I'm the one doing the proof) I wrote it in python. Now I'd like a high-performance implementation. Can you give me some pointers on porting this function to nim?
#C is a set of signed ints
def negate(C):
return set(map(lambda l: -l, C))
#phi is a list of sets of signed ints, n is an unsigned int, m is an unsigned int, epsilon is a list of unsigned bigints
def memoized(phi,n,m,epsilon):
if filter(lambda c: not c, phi):
return 2**n
for i in range(m - 1, -1, -1):
phiprime = [C - phi[i] for C in phi[i+1:] if not negate(C) & phi[i]]
epsilonprime = map(lambda x: epsilon[x + len(phi) - len(phiprime)]/2**len(phi[i]), range(0,len(phiprime)))
mprime = len(phi)
for x in range(len(phi) - 1, i, -1):
if not phi[x] & phi[i] and not negate(phi[x]) & phi[i]:
mprime = x
else:
break
mprime -= len(phi) - len(phiprime)
epsilon[i] = 2**(n - len(phi[i])) - memoized(phiprime, n - len(phi[i]), mprime, epsilonprime)
return sum(epsilon)Nim doesn't have native Big Int datatypes.
Implemented in Nim, not very performant: https://github.com/def-/nim-bigints
Wrapper for GMP, very performant: https://github.com/jovial/nim-gmp
Slicing a sequence will create a copy of the sliced contents.
Python copies too:
x = [1, 2, 3]
y = x[:]
y is x # false
Wait... Nim doesn't have lambda? What would the macro to implement lambda be?
There are anonymous procs, but they're not as comfortable to use, mainly because you need to supply the argument and return types. Also, the thread poster asked for "high performance", so lambdas wouldn't be ideal.
A question for you: is a collection false or true depending on whether its empty or not in nim like in python? I really like that, as you can tell I use it all the time.
P.S. I also corrected one other mistake on the second to last line related to removing the calls variable. I promise there aren't any others :).
def: Also, the thread poster asked for "high performance", so lambdas wouldn't be ideal.
I generally use iterators with an enumerate template for this purpose:
template enumerate(s: untyped): auto =
block:
iterator temp(): auto = s
var result = newSeq[type(temp())]()
for item in temp():
add(result, item)
result
import sequtils
proc mapExample =
let x = toSeq(1..10)
let y = enumerate do:
for i in x:
yield i * i
echo y
proc filterExample =
let x = toSeq(1..10)
let y = enumerate do:
for i in x:
if i mod 2 == 0:
yield i
echo y
proc filterMapExample =
let x = toSeq(1..10)
let y = enumerate do:
for i in x:
if i mod 2 == 0:
yield i*i
echo y
mapExample()
filterExample()
filterMapExample()
Edit: Copied and pasted the wrong version of enumerate.
RaphaelHythloday: Also, regarding the GMP wrapper, wouldn't it be easy to make macros that let you use the bigints with the primitive operators?
I've taken a first stab at that here if someone is interested in tidying this up.
Note that you may have to pass along a -I option to --passC and a -L option to --passL so that the C compiler knows where to find the include file and the library. The code intentionally does not use the dynlib pragma, because when you're working with GMP, you often want to control exactly which version of the library you're using, which is difficult to do with dynlib's dlopen()-based approach.
Using the below template which is mashed together from various templates in sequtils.nim, it was of the similar speed as mapIt() :-)
Of course, you can use mapFilterIt for mapping, filtering and mapFiltering
template mapFilterIt(seq1, typ, op, pred: expr): expr {.immediate.} =
var result {.gensym.}: seq[typ] = @[]
for it {.inject.} in items(seq1):
if pred: result.add(op)
result
let x = toSeq(1..10)
# mapping
var y = x.mapFilterIt(int, it*it, true)
echo y # @[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
# filtering
y = x.mapFilterIt(int, it, (it mod 2 == 0))
echo y # @[2, 4, 6, 8, 10]
# mapFiltering
y = x.mapFilterIt(int, it*it, (it mod 2 == 0))
echo y # @[4, 16, 36, 64, 100]
mapIt and enumerate generate the same code, so if there's a performance difference [1], there's something strange going on (did you compile with the same options each time?). The point of enumerate is that it's more general and doesn't rely on a hardcoded variable name. The downside is that it's generally more code to write.
[1] Unless you used the in-place version of mapIt, which has different semantics.
proc mapExample1 = let x = toSeq(1..10) let y = x.mapIt(int, it*it) proc mapExample2 = let x = toSeq(1..10) let y = x.mapFilterIt(int, it*it, true)