我有这个功能的多个问题。 这是数据结构和算法课程的奖金问题的一部分,我在这一个问题上花了很多时间,我真的很想让它工作并理解正在发生的事情。
有一个主要问题,导致了几个小问题......这个问题的名字是JavaScript。 我们以前从未用JavaScript编程,但出于某种原因我们必须使用它。
该函数必须通过测试(这一个和斐波纳契),其结构如下:
var fn = (n) => 2 * n var m_fn = memoize(fn) expect(m_fn(18)).to.equal(fn(18))所以我必须传递我想要memoize的函数作为memoize函数的参数,memoize函数必须返回一个函数。 我不允许以任何其他方式这样做。
我完成了所有的阅读并研究了memoize函数,但所有的实现都采用了不同的方法。
基本上,我明白我必须做什么,但我不太明白。 我知道memoize函数应该做什么,但我不明白如何使用memoize函数调整原始函数。 这是我到目前为止/我没有的东西:
我知道这是错的。 但我想我错过了一些重要的东西。 我应该返回一个函数,但我正在返回值...
在测试中,它是写入var m_fn = memoize(fn),所以memoize函数传递fn,然后返回一个新函数,但在我的memoize中,我返回fn(n)的值,所以我做错了什么.. 。
/** * Creates a memoized version of the function fn. It is assumed that fn is a referentially transparent * function. * @param {function} fn Some referentially transparent function that takes a basic datatype (i.e. number / string) * @returns {function} A new function that is the memoized version of fn. It never calculates the result of * a function twice. */ memoize: (fn) => { //here we enter the function that we want to memoize var memory = []; //we need to create an array to hold the previously calculated values, length n (parameter of fn) if(this.n > memory.length){ //Check to see if this particular value is in the array already. return memory[this.n]; //How do I access the integer parameter that was passed through fn though? Is this correct? } else{ // if not, we want to save it and return it var result = fn(this.n); memory.push(result); return result; }}
I am having multiple problems with this function. It's part of a bonus question for a Data Structures and Algorithms class and I've invested so much time in this one problem, that I'd really like to get it to work and understand what's going on.
There is one main problem, which has caused several little ones...this problem's name is JavaScript. We've never programmed in JavaScript before, but for some reason we have to use it.
The function has to pass tests (this one and fibonacci), which are structured like this:
var fn = (n) => 2 * n var m_fn = memoize(fn) expect(m_fn(18)).to.equal(fn(18))So I have to pass the function I want to memoize as a parameter of the memoize function and the memoize function has to return a function. I am not allowed to do it any other way.
I did all of the reading and researched the memoize function, but all of the implementations take a different approach.
Basically, I understand what I have to do, but I don't quite understand HOW. I know what the memoize function should do, but I don't understand how to adjust the original function using my memoize function. This is what I have so far/what I don't have:
I know it's wrong. But I think I'm missing something major. I am supposed to return a function, but I am returning values...
In the test, it's writen var m_fn = memoize(fn), so the memoize function passes fn, then returns a new function, but in my memoize, I am returning values for fn(n), so I AM doing something wrong...
/** * Creates a memoized version of the function fn. It is assumed that fn is a referentially transparent * function. * @param {function} fn Some referentially transparent function that takes a basic datatype (i.e. number / string) * @returns {function} A new function that is the memoized version of fn. It never calculates the result of * a function twice. */ memoize: (fn) => { //here we enter the function that we want to memoize var memory = []; //we need to create an array to hold the previously calculated values, length n (parameter of fn) if(this.n > memory.length){ //Check to see if this particular value is in the array already. return memory[this.n]; //How do I access the integer parameter that was passed through fn though? Is this correct? } else{ // if not, we want to save it and return it var result = fn(this.n); memory.push(result); return result; }}
最满意答案
实际上,您需要返回一个函数。
其次,数组不是memory的理想结构,因为它需要线性时间来查找其中的参数值。 我建议使用Map来实现这个目的。 它有has() , get()和set()方法,它们在接近恒定的时间内运行:
function memoize(fn) { var memory = new Map(); return function(arg) { if (memory.has(arg)) { console.log('using memory'); return memory.get(arg); } else { var result = fn(arg); memory.set(arg, result); return result; } }; } var fn = (n) => 2 * n var m_fn = memoize(fn) console.log(fn(18)); console.log(m_fn(18)); console.log(m_fn(18)); // outputs also "using memory"Indeed, you need to return a function.
Secondly, an array is not the ideal structure for memory, because it takes linear time to find an argument value in it. I would suggest to use a Map for this, which is ideal for such purposes. It has has(), get() and set() methods which run in near-constant time:
function memoize(fn) { var memory = new Map(); return function(arg) { if (memory.has(arg)) { console.log('using memory'); return memory.get(arg); } else { var result = fn(arg); memory.set(arg, result); return result; } }; } var fn = (n) => 2 * n var m_fn = memoize(fn) console.log(fn(18)); console.log(m_fn(18)); console.log(m_fn(18)); // outputs also "using memory"
更多推荐
发布评论