Re:Data structures and algorithms I actually used while work...
by nipxx on Wednesday July 15, 2020 @03:54AM
(#23842433)
As sad as it is, I get 90% of my algorithm work done with sorted arrays and binary search. Rarely I need more fancy stuff.
[ Parent
| on HN ]
Re:Data structures and algorithms I actually used while work...
by tzs on Wednesday July 15, 2020 @09:40AM
(#23845050)
I sometimes suspect that everything is really just a sorting problem.
For example, here is a shell script that takes an input file consisting of lines of the form
X Y
where X and Y are integers representing the X and Y coordinates of live cells in a Conway's Life grid, and outputs the next generation in the same format. It runs in O(n log n) where n is the number of live cells, and it is really just sorting. > alive.$$
while read cells
do
echo $cells >> alive.$$
set x $cells
x=$2
y=$3
echo $x $((y-1))
echo $x $((y+1))
echo $((x-1)) $((y-1))
echo $((x-1)) $y
echo $((x-1)) $((y+1))
echo $((x+1)) $((y-1))
echo $((x+1)) $y
echo $((x+1)) $((y+1))
done | sort | uniq -c > neighbors.$$
grep '^ *3' < neighbors.$$ | sed -e 's/^ *[0-9].//'
grep '^ *2' < neighbors.$$ | sed -e 's/^ *[0-9].//' > has2.$$
sort alive.$$ -o alive.$$
comm -12 has2.$$ alive.$$
rm has2.$$ neighbors.$$ alive.$$