A solution to speed up and manage memory

Questions / Help
1

hello friends
i want to do an operation on all 11-digit numbers
due to the large number of digits, I have to do this in the best possible way to make the program run very fast
i send all the numbers to a function and if it is True, I save that number in the text file.
my problem is managing memory and program speed
for example, it only takes a long time to make a list of numbers from 00000000001 to 99999999999.
I know that system languages like c, etc. are great for such programs
But I want to ask your opinion to see if you know a way to speed up the program in the language of Elixir

Thanks

2

Working your way through 100 billion elements will indeed take some time. The most trivial optimizations that come to mind:

  • To keep memory usage low, use streams instead of enums, something like
    Stream.filter(0..999900009, &test/1)
  • Your problem is highly paralelliizable: split your input into a number of chunks and spawn separate processes for doing the work. Use something like Flow to make that trivial.

Having said this, I can’t help to wonder if you are doing the right thing - is brute forcing all possible numbers through a test function really the only way to attack this problem? Is there not some kind of pattern in your data that you can leverage to optimize this problem? Without having more background info on your problem it’s hard to help you out any further.

3 Likes
3

Thanks for the reply
This is my function, I want to process all 10-digit numbers

def check(input) do
    digit = Integer.digits(input)
    last = Enum.at(digit, -1)
    sum = digit |> List.delete_at(-1) |> Enum.reverse() |> Enum.with_index(2) |> Enum.reduce(0, fn {num, key}, sum -> key * num + sum end) |> rem(11)
    (sum >= 2 and 11 - sum == last) or (sum <= 2 and sum == last)
  end
4

This code is also in Python
Optimized version

import time
import itertools

start = time.time()
counter = 0
code_list = {*()}
for number in itertools.product("0123456789", repeat=9):
    counter += 1
    mod = sum([int(number[i]) * (10 - i) for i in range(0, 9)]) % 11
    if mod < 2:
        code_list.add("".join(number) + str(mod))
    else:
        code_list.add("".join(number) + str(11 - mod))
    if len(code_list) % 10000000 == 0:
        f = open("final.txt", "a+")
        while len(code_list) > 0:
            item = code_list.pop()
            f.writelines(item + "\n")
        f.close()
        print("memory flush at " + str(time.time() - start) + " sec, " + str(counter) + " checked")
5

That looks suspiciously close to Luhn’s algorithm to checksum credit card numbers. What is this for?

2 Likes
6

its right
this is Luhn algorithm
but not for credit card

7

Also reminds me of the “11 test” used for dutch bank account and social security numbers.

Well, if this is a one-off job, it shoud be not too bad: a naive single threaded implementation finishes in about 83 minutes on my machine, and you’ll end up with a file of about 100Mb size with all valid numbers in ASCII,

2 Likes
8

If you are very curious, i am on a research project for 10-digit numbers or the national code of Iranians
And I want to find the number of people in each city and … and express it in our research project :smile:
For example, in a city of 20k people, several valid national codes can be created

9 
def check(input) do
    digit = Integer.digits(input)
    [ last | rest ] = Enum.reverse(digit)
    sum = rest |> Enum.with_index(2) |> Enum.reduce(0, fn {num, key}, sum -> key * num + sum end) |> rem(11)
    (sum >= 2 and 11 - sum == last) or (sum <= 2 and sum == last)
  end

That should be a little more efficient than traversing the list multiple times.

2 Likes
10

Note that this isn’t what the “optimized” Python version does - for a given 9-digit prefix, there are ten 10-digit numbers but only one of them passes the check so it calculates the 10th digit.

Here’s a pretty direct translation of that Python code, which splits the work across all the available CPUs:

defmodule Calc do
  def ranges_to(n, size) do
    Stream.unfold(0, fn start ->
      {start..start+size, start+size+1}
    end)
    |> Stream.take_while(& &1.first <= n)
  end

  def write_numbers(r) do
    r
    |> with_padding()
    |> with_final_digit()
    |> Stream.intersperse("\n")
    |> Stream.into(File.stream!("out-#{div(r.first, 1_000_000)}.txt"))
    |> Stream.run()
  end

  def check_digit(n) do
    n
    |> String.codepoints()
    |> Enum.map(&String.to_integer/1)
    |> Enum.with_index()
    |> Enum.map(fn {d, i} -> d * (10-i) end)
    |> Enum.sum()
    |> rem(11)
  end

  def final_digit(n) do
    check = check_digit(n)

    if check < 2 do
      "#{check}"
    else
      "#{11 - check}"
    end
  end

  def with_padding(s) do
    Stream.map(s, &String.pad_leading(Integer.to_string(&1), 10, "0"))
  end

  def with_final_digit(s) do
    Stream.map(s, &(&1 <> final_digit(&1)))
  end
end

Calc.ranges_to(999_999_999, 1_000_000)
|> Task.async_stream(&Calc.write_numbers/1, ordered: false, timeout: :infinity)
|> Stream.run()

The trickiest part is dividing up the work; if the chunks are too small, starting & stopping a process per-chunk will take up too much of the runtime.

3 Likes