0

How to pass map by reference during Memoization?

*Passing map by pointer works fine but I need to keep it on Stack any idea how can I achieve that.

first method fib works properly but the function fibRef not working the map not accepting the pair.

I could understand it's something related to RValue and LValue.

*

//
//  Fib.cpp
// 
//
//  Created by Youssef Hanna on 1/26/21.
//

#include <stdio.h>
#include <iostream>
#include <map>


// works fine
long long fib(int n, std::map<int, long long> *values = new std::map<int , long long>())
{
  if (n <= 2 )
    return n;
    
    if(values->find(n) != values->end())
        return values->at(n);
    
    long long result =  fib(n-1,values) + fib(n-2,values);
    values->insert(std::pair<int, long long>(n,result));
    
    
    return result;
}

// Error values not added to the map
int fibRef(int n, std::map<int, int> values = {})
{
  if (n <= 2)
    return 1;
    
    if(values.find(n) != values.end())
        return values.at(n);
    
    int result =  fibRef(n-1,values) + fibRef(n-2,values);
    values.insert(std::pair<int, int>(n,result));
    
    
    return result;
}


// Best option at the moment 
long long fibWithPassingMap(int n, std::map<int, long long> & values)
{
  if (n <= 2)
    return 1;
    
    if(values.find(n) != values.end())
        return values.at(n);
    
    long long result =  fibWithPassingMap(n-1,values) + fibWithPassingMap(n-2,values);
    values.insert(std::pair<int, long long>(n,result));
    
    
    return result;
}



void runFibTest(){
    
    
    
    std::cout<<"\n"<<fib(10) << "\n" ;
    std::cout<<"\n"<<fib(20) << "\n" ;
    std::cout<<"\n"<<fib(30) << "\n" ;
    std::cout<<"\n"<<fib(100) << "\n" ;
    std::cout<<"\n"<<fib(250) << "\n" ;

    std::cout<<"\n"<<fib(1000) << "\n" ;
   
    std::map<int , long long> map;
    std::cout<<"\n"<<fibWithPassingMap(100, map) << "\n" ;
    std::cout<<"\n"<<fibWithPassingMap(90, map) << "\n" ;

    std::cout<<"\n"<<fibWithPassingMap(25, map) << "\n" ;

    std::cout<<"\n"<<fibWithPassingMap(30, map) << "\n" ;

    std::cout<<"\n"<<fibWithPassingMap(1020, map) << "\n" ;

    map.clear();
    

    std::cout<<"\n"<<fibRef(100) << "\n" ;  // too long because memoization not working

    

    
    
}

Thanks in advance

ymyh
  • 11
  • 6
  • 3
    `std::map` will allocate its internal data structure (i.e., red-black tree) on the heap -- it is possible to create a allocator that uses the stack (https://stackoverflow.com/questions/8049657/stack-buffer-based-stl-allocator), but this is in general a bad idea. Another note, instead of passing by ptr, use pass by reference `std::map& values = std::map()` -- much simpler and avoids memory leaks, etc,,, – wcochran Jan 29 '21 at 16:28
  • @wcochran you can't have a default initializer for a non-const reference parameter. – Patrick Roberts Jan 29 '21 at 16:31
  • Aren't your missing the `&` in the `fibRef` just before `values`? – Surt Jan 29 '21 at 16:32
  • Where do you `delete` the `std::map` you create on a default-arg call to `fib`? – Nathan Pierson Jan 29 '21 at 16:36
  • 2
    I'm also not convinced that the first version is working correctly because the 1000th fibonacci number is probably overflowing an `int` so you're getting undefined behavior. – Nathan Pierson Jan 29 '21 at 16:49
  • @PatrickRoberts yeah you are right ... this default initialization should be avoid anyway. – wcochran Jan 29 '21 at 19:54
  • Thanks for your reply but if I should avoid the default initialization how could I do the Memoization. Regarding the 100th fib it’s working without any problem with passing the map as a pointer.do you have an example for passing a referenced map? – ymyh Jan 31 '21 at 18:53
  • I changed the code to be Fib (100) instead of 1000th because 1000th was crashing. – ymyh Jan 31 '21 at 18:58
  • For the sizes of maps that make sense to put on the stack - hundreds or thousands of items at most - you may do best just having a sorted array and doing a binary search. For even smaller maps (128 or less items), the searching can be highly parallelized, ideally by the compiler, and even the sorting step won’t be necessary. – Kuba hasn't forgotten Monica Jan 31 '21 at 21:13
  • So the best option I found at the moment is to pass the map by reference. so I have full control of the map and I could clear it after it finished. please let me know if they're a better option. Thanks in advance – ymyh Feb 01 '21 at 11:07

0 Answers0