# Naive lookup table with lots of allocations

**URL:** <https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457>\
**Category:** Performance\
**Created:** [July 28, 2021, 6:55pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457 "2021-07-28T18:55:53Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [July 28, 2021, 6:55pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/1 "2021-07-28T18:55:53Z")

</div>

Hi there,

going through project euler problems, I’ve implemented a working solution for problem 17:

```julia
function num2letters(num)
    nums = Dict(
        0 => "", 1 => "one", 2 => "two", 3 => "three", 4 => "four", 5 => "five",
        6 => "six", 7 => "seven", 8 => "eight", 9 => "nine", 10 => "ten",
        11 => "eleven", 12 => "twelve", 13 => "thirteen", 14 => "fourteen",
        15 => "fifteen", 16 => "sixteen", 17 => "seventeen", 18 => "eighteen",
        19 => "nineteen", 20 => "twenty", 30 => "thirty", 40 => "forty",
        50 => "fifty", 60 => "sixty", 70 => "seventy", 80 => "eighty",
        90 => "ninety", 100 => "hundred", 1000 => "thousand"
)

    if num <= 20
        return length(nums[num])
    elseif num < 100
        tens, units = divrem(num, 10)
        return length(nums[tens * 10]) + num2letters(units)
    elseif num < 1000
        hundreds, rest = divrem(num, 100)
        if rest != 0
            return num2letters(hundreds) + length(nums[100]) + length("and") + num2letters(rest)
        else
            return num2letters(hundreds) + length(nums[100])
        end
    else
        thousands, rest = divrem(num, 1000)
        return num2letters(thousands) + length(nums[1000])
    end
end

function Problem17()
    #=
    If the numbers 1 to 5 are written out in words: one, two, three, four,
    five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

    If all the numbers from 1 to 1000 (one thousand) inclusive were written
    out in words, how many letters would be used?

    NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
    forty-two) contains 23 letters and 115 (one hundred and fifteen) contains
    20 letters. The use of "and" when writing out numbers is in compliance
    with British usage.
    =#
    n = 1000
    letters = 0
    for num in 1:n
        letters += num2letters(num)
    end
    return letters
end

```

It takes almost 7 ms and does 25k allocations. That’s the same time I’m getting in Python with almost identical code.

How can I do better?

Thx in advance.

---

<div class="post-metadata">

**Author:** ![pdeffebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pdeffebach/32/10320_2.png) [@pdeffebach](https://discourse.julialang.org/u/pdeffebach)\
**Post date:** [July 28, 2021, 7:01pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/2 "2021-07-28T19:01:38Z")

</div>

Well for one, you are re-creating the `Dict` every time you call `num2letters`. But it seems constant.

Make the dictionary an input to the function.

---

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [July 28, 2021, 7:08pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/3 "2021-07-28T19:08:37Z")

</div>

I did already that and time (33 vs 7) and allocations (43k vs 25k) were worse ☹

---

<div class="post-metadata">

**Author:** ![sostock](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sostock/32/5546_2.png) [@sostock](https://discourse.julialang.org/u/sostock)\
**Post date:** [July 28, 2021, 7:20pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/4 "2021-07-28T19:20:59Z")

</div>

For me, creating the `Dict` in `Problem17` instead of `num2letters` reduces allocations from 25k to 18k. What did you do?

---

<div class="post-metadata">

**Author:** ![pdeffebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pdeffebach/32/10320_2.png) [@pdeffebach](https://discourse.julialang.org/u/pdeffebach)\
**Post date:** [July 28, 2021, 7:22pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/5 "2021-07-28T19:22:03Z")

</div>

Really? The following doesn’t make it faster?

```julia
function num2letters(num, nums)

    if num <= 20
        return length(nums[num])
    elseif num < 100
        tens, units = divrem(num, 10)
        return length(nums[tens * 10]) + num2letters(units, nums)
    elseif num < 1000
        hundreds, rest = divrem(num, 100)
        if rest != 0
            return num2letters(hundreds, nums) + length(nums[100]) + length("and") + num2letters(rest, nums)
        else
            return num2letters(hundreds, nums) + length(nums[100])
        end
    else
        thousands, rest = divrem(num, 1000)
        return num2letters(thousands, nums) + length(nums[1000])
    end
end

function Problem17()

    nums = Dict(
        0 => "", 1 => "one", 2 => "two", 3 => "three", 4 => "four", 5 => "five",
        6 => "six", 7 => "seven", 8 => "eight", 9 => "nine", 10 => "ten",
        11 => "eleven", 12 => "twelve", 13 => "thirteen", 14 => "fourteen",
        15 => "fifteen", 16 => "sixteen", 17 => "seventeen", 18 => "eighteen",
        19 => "nineteen", 20 => "twenty", 30 => "thirty", 40 => "forty",
        50 => "fifty", 60 => "sixty", 70 => "seventy", 80 => "eighty",
        90 => "ninety", 100 => "hundred", 1000 => "thousand"
    )
    #=
    If the numbers 1 to 5 are written out in words: one, two, three, four,
    five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

    If all the numbers from 1 to 1000 (one thousand) inclusive were written
    out in words, how many letters would be used?

    NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
    forty-two) contains 23 letters and 115 (one hundred and fifteen) contains
    20 letters. The use of "and" when writing out numbers is in compliance
    with British usage.
    =#
    n = 1000
    letters = 0
    for num in 1:n
        letters += num2letters(num, nums)
    end
    return letters
end

```

I get the following timing

```julia
julia> @btime Problem17()
  67.200 μs (7 allocations: 1.73 KiB)
21124

```

---

<div class="post-metadata">

**Author:** ![hendri54](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hendri54/32/9621_2.png) [@hendri54](https://discourse.julialang.org/u/hendri54)\
**Post date:** [July 28, 2021, 7:23pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/6 "2021-07-28T19:23:06Z")

</div>

I would avoid the Dict entirely.

```julia
function length_up_to_ten(x)
  if x == 0
    return 0
  elseif x in (1, 2, 6, 10)
    return 3
  elseif x in (4, 9)
    return 4
  elseif x in (3, 8)
    return 5
  end
end

function length_up_to_twenty(x)
  [...]
end

```

Then in the main function call the appropriate sub-function depending on the value of num (or the parts it is divided into).

---

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [July 28, 2021, 7:27pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/7 "2021-07-28T19:27:53Z")

</div>

aha, I put the dictionary outside of both functions

---

<div class="post-metadata">

**Author:** ![pdeffebach](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pdeffebach/32/10320_2.png) [@pdeffebach](https://discourse.julialang.org/u/pdeffebach)\
**Post date:** [July 28, 2021, 7:30pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/8 "2021-07-28T19:30:39Z")

</div>

Read through the [performance tips](https://docs.julialang.org/en/v1/manual/performance-tips/) in the Julia manual to understand why that’s a bad idea, as well as learn more ways to speed up code.

---

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [July 28, 2021, 7:35pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/9 "2021-07-28T19:35:51Z")

</div>

Thx, will do 🙂

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 28, 2021, 10:24pm UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/10 "2021-07-28T22:24:35Z")

</div>

Yeah, something like this. For a smaller change in the algorithm, store the length of the words in the dict instead of the words themselves.

---

<div class="post-metadata">

**Author:** ![hendri54](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hendri54/32/9621_2.png) [@hendri54](https://discourse.julialang.org/u/hendri54)\
**Post date:** [July 29, 2021, 11:06am UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/11 "2021-07-29T11:06:18Z")

</div>

But then, if the goal is to count the number of letter for the specific set of numbers 1:1000, the better approach is do some math instead.  
There are 10 thousand terms. Each has length “length of number between 1 and 9” plus length of the word “thousand”.  
For each thousand term, there are ten hundred terms. Figure out the length of each (essentially “length of 1:9” + length of word “hundred”).  
For each hundred term, we get the length of 0:99.  
Then add up: length of thousands + 10_length of hundreds + 100_length of (0:99)

---

<div class="post-metadata">

**Author:** ![Gabrielforest](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gabrielforest/32/27538_2.png) [@Gabrielforest](https://discourse.julialang.org/u/Gabrielforest)\
**Post date:** [May 30, 2022, 3:30am UTC](https://discourse.julialang.org/t/naive-lookup-table-with-lots-of-allocations/65457/12 "2022-05-30T03:30:48Z")

</div>

I wrote this code which is not faster but it takes less time to write the code (just in case someone would like to know a shorter solution)

```julia
function total_letters( n::Int64 )
  v = [SpelledOut.spelled_out( i, lang = :en_UK ) for i in 1:n]
  sum( length.( v ) ) - ( sum( count.( " ", v ) ) + sum( count.( "-", v ) ) )
end
total_letters( 1000 )

```