C# 0.135s
C# based on Alistair Buxton's plain python: 0.278s
Parallelised C#: 0.135s
Python from the question: 5.907s
Alistair's plain python: 0.853s
I'm not actually certain this implementation is correct - its output is different, if you look at the results down at the bottom.
There's certainly more optimal algorithms. I just decided to use a very similar algorithm to the Python one.
Single-threaded C
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConvolvingArrays
{
static class Program
{
static void Main(string[] args)
{
int n=6;
int iters = 1000;
int firstzero = 0;
int bothzero = 0;
int[] arraySeed = new int[] {-1, 1};
int[] randomSource = new int[] {-1, 0, 0, 1};
Random rand = new Random();
foreach (var S in Enumerable.Repeat(arraySeed, n+1).CartesianProduct())
{
for (int i = 0; i < iters; i++)
{
var F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
while (!F.Any(f => f != 0))
{
F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
}
if (Enumerable.Zip(F, S.Take(n), (f, s) => f * s).Sum() == 0)
{
firstzero++;
if (Enumerable.Zip(F, S.Skip(1), (f, s) => f * s).Sum() == 0)
{
bothzero++;
}
}
}
}
Console.WriteLine("firstzero {0}", firstzero);
Console.WriteLine("bothzero {0}", bothzero);
}
// itertools.product?
// http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/
static IEnumerable<IEnumerable<T>> CartesianProduct<T>
(this IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IEnumerable<T>> emptyProduct =
new[] { Enumerable.Empty<T>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
select accseq.Concat(new[] { item }));
}
}
}
Parallel C#:
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace ConvolvingArrays
{
static class Program
{
static void Main(string[] args)
{
int n=6;
int iters = 1000;
int firstzero = 0;
int bothzero = 0;
int[] arraySeed = new int[] {-1, 1};
int[] randomSource = new int[] {-1, 0, 0, 1};
ConcurrentBag<int[]> results = new ConcurrentBag<int[]>();
// The next line iterates over arrays of length n+1 which contain only -1s and 1s
Parallel.ForEach(Enumerable.Repeat(arraySeed, n + 1).CartesianProduct(), (S) =>
{
int fz = 0;
int bz = 0;
ThreadSafeRandom rand = new ThreadSafeRandom();
for (int i = 0; i < iters; i++)
{
var F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
while (!F.Any(f => f != 0))
{
F = Enumerable.Range(0, n).Select(_ => randomSource[rand.Next(randomSource.Length)]);
}
if (Enumerable.Zip(F, S.Take(n), (f, s) => f * s).Sum() == 0)
{
fz++;
if (Enumerable.Zip(F, S.Skip(1), (f, s) => f * s).Sum() == 0)
{
bz++;
}
}
}
results.Add(new int[] { fz, bz });
});
foreach (int[] res in results)
{
firstzero += res[0];
bothzero += res[1];
}
Console.WriteLine("firstzero {0}", firstzero);
Console.WriteLine("bothzero {0}", bothzero);
}
// itertools.product?
// http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/
static IEnumerable<IEnumerable<T>> CartesianProduct<T>
(this IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IEnumerable<T>> emptyProduct =
new[] { Enumerable.Empty<T>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
select accseq.Concat(new[] { item }));
}
}
// http://stackoverflow.com/a/11109361/1030702
public class ThreadSafeRandom
{
private static readonly Random _global = new Random();
[ThreadStatic]
private static Random _local;
public ThreadSafeRandom()
{
if (_local == null)
{
int seed;
lock (_global)
{
seed = _global.Next();
}
_local = new Random(seed);
}
}
public int Next()
{
return _local.Next();
}
public int Next(int maxValue)
{
return _local.Next(maxValue);
}
}
}
Test output:
Windows (.NET)
The C# is much faster on Windows. Probably because .NET is faster than mono.
User and sys timing doesn't seem to work (used git bash for timing).
$ time /c/Python27/python.exe numpypython.py
firstzero 27413
bothzero 12073
real 0m5.907s
user 0m0.000s
sys 0m0.000s
$ time /c/Python27/python.exe plainpython.py
firstzero 26983
bothzero 12033
real 0m0.853s
user 0m0.000s
sys 0m0.000s
$ time ConvolvingArrays.exe
firstzero 28526
bothzero 6453
real 0m0.278s
user 0m0.000s
sys 0m0.000s
$ time ConvolvingArraysParallel.exe
firstzero 28857
bothzero 6485
real 0m0.135s
user 0m0.000s
sys 0m0.000s
Linux (mono)
bob@phoebe:~/convolvingarrays$ time python program.py
firstzero 27059
bothzero 12131
real 0m11.932s
user 0m11.912s
sys 0m0.012s
bob@phoebe:~/convolvingarrays$ mcs -optimize+ -debug- program.cs
bob@phoebe:~/convolvingarrays$ time mono program.exe
firstzero 28982
bothzero 6512
real 0m1.360s
user 0m1.532s
sys 0m0.872s
bob@phoebe:~/convolvingarrays$ mcs -optimize+ -debug- parallelprogram.cs
bob@phoebe:~/convolvingarrays$ time mono parallelprogram.exe
firstzero 28857
bothzero 6496
real 0m0.851s
user 0m2.708s
sys 0m3.028s
