Как написать функцию cheapStoreForRecipe наиболее эффективным способом?

Question

Как мне решить это наиболее эффективным способом? Должны ли мы работать с .reduce () и этими методами или мы должны использовать classi c for в l oop, чтобы перебрать ключи в allStore и вычислить его по рецепту?

var soup = { //recipe
    potato: 3,
    onion: 1,
    corn: 5
};

var edoka = {
    cheese: 8,
    corn: 3,
    meat: 6,
    onion: 4,
    pea: 1,
    oregano: 7,
    potato: 5,
    tomato: 6
};

var were = {
    cheese: 6,
    corn: 2,
    meat: 9,
    onion: 5,
    pea: 2,
    oregano: 6,
    potato: 3,
    tomato: 3
};

var brutto = {
    cheese: 6,
    corn: 2,
    meat: 9,
    onion: 5,
    pea: 2,
    oregano: 8,
    potato: 3,
    tomato: 4
};

var allStores = { // this is an example of a "storeCollection"
    Brutto: brutto,
    Edoka: edoka,
    Were: were,
};

function cheapestStoreForRecipe(recipe, storeCollection){
    // make it return the key for the store in storeCollection
    // that has the cheapest total cost for recipe. Feel free
    // to use costOfRecipe inside this function!
}

Answer 1

Чтобы рассчитать стоимость рецепта, вам нужно сложить значения массива, состоящего из пересечения ключей рецепта и ключей продуктов каждого магазина. Но это ваша домашняя работа, и вы должны сделать это сами.

Что касается эффективности различных способов суммирования элементов массива, for является наиболее эффективным в длинных массивах.

Я сделал небольшую демонстрацию ниже, сравнивая

• для
• для ... 1013 *
• forEach
• уменьшить

const add = (a, b) => a + b;

const functionsObj = {
  usingFor: async(array) => {

    return new Promise(res => {
      let result = 0;
      for (let i = 0; i < array.length; i++) {
        result += array[i];
      }
      res(result);
    });
  },
  usingForeach: async(array) => {
    return new Promise(res => {
      let result = 0;
      array.forEach(number => {
        result += number;
      })
      res(result);
    });
  },

  usingReduce: async(array) => {
    return new Promise(res => {
      const result = array.reduce(add);
      res(result);
    });
  },
  usingForOf: async(array) => {
    return new Promise(res => {
      let result = 0;
      for (let i of array) {
        result += i;
      }
      res(result);
    });
  }
};
const Arr10M = [];
for (let j = 0; j < 10000000; j++) {
  Arr10M.push(
    1 + parseInt(40 * Math.random(), 10)
  );
}
const Arr10K = Arr10M.slice(0, 10000);

async function runTests(method, arr, attempts = 300) {
  let results = [];
  for (let attempt of arr.slice(0, attempts)) {
    performance.mark('start');
    await functionsObj[method](arr);
    performance.mark('end');
    results.push(performance.measure(method, 'start', 'end').duration);
    performance.clearMeasures();
    performance.clearMarks();
  }
  return new Promise(res => {
    let min = 1 * Number(Math.min(...results)).toFixed(6),
      max = 1 * Number(Math.max(...results)).toFixed(6);

    window.setTimeout(() => {
      res([min, max]);
    }, 1000 - 1 * max);
  });

}
(async() => {


  let results = {},
    methods = ['usingFor', 'usingForOf', 'usingReduce', 'usingForeach'];
  for (let method of methods) {
    let [
      min_10K_elements,
      max_10K_elements
    ] = await runTests(method, Arr10K), [
        min_10M_elements,
        max_10M_elements
      ] = await runTests(method, Arr10M, 3),
      result = {
        min_10K_elements,
        max_10K_elements,
        min_10M_elements,
        max_10M_elements
      };

    results[method] = result;
    console.log({
      method,
      ...result
    });
  }
  console.table(results);


  return;
})();

Если вы откроете devtools в своем браузере, чтобы увидеть результаты в таблице, вы заметите, что for всегда самый быстрый, где reduce и forEach равны +. Разница незначительна при тестировании массивов из 10К элементов (и может зависеть от одновременных процессов в браузере или даже на вашем компьютере).

При тестировании массива из 10М элементов производительность for составляет 20x и в 30 раз по сравнению с reduce и forEach.

Чистый код превосходит раннюю переоптимизацию, но если ваша домашняя работа имеет грубую производительность, у вас есть настоящий эталон.

Answer 2

Вот решение, которое поможет вам изучить, как использовать Array.reduce. Это может быть не самым эффективным, но отсюда вы можете разработать собственное решение. Чтобы сделать это более эффективным, вам следует продолжить работу с концепцией, чтобы получить необходимые вам результаты с точки зрения времени обработки или сложности.

Пример Repl

cheapestStoreForRecipe принимает два аргумента: recipe и storeCollection. Метод возвращает список магазинов с накладными для рецепта, который включает стоимость каждого товара и общую стоимость.

Во-первых, storeCollection перебирает все хранилища в коллекции. Во-вторых, для каждого магазина пункты рецепта повторяются. При наличии предмета рецепта, который соответствует предмету магазина, рассчитываются значения quantity, unit и total для предмета; Затем рассчитывается общая стоимость каждого рецепта.

function cheapestStoreForRecipe(recipe, storeCollection){
  return Object.entries(storeCollection)
    .reduce((_storeCollection, [storeName, storeInventory]) => {
      let storeInvoice = Object.entries(recipe)
        .reduce((_recipe, [itemName, itemQuantity]) => {
          let storeInventoryItem = storeInventory[itemName]
          if(storeInventoryItem) {
            _recipe.invoice[itemName] = {
              quantity: itemQuantity,
              unit: storeInventoryItem,
              total: itemQuantity * storeInventoryItem,
            }
            _recipe.total += _recipe.invoice[itemName].total
          }
          return _recipe
        }, {
          invoice: {},
          total: 0,
        })
      _storeCollection[storeName] = storeInvoice
      return _storeCollection
    }, {
      Brutto: {},
      Edoka: {},
      Were: {},
    })
}

{
  "Brutto": {
    "invoice": {
      "potato": {
        "quantity": 3, 
        "unit": 3,
        "total": 9
      },
      "onion": {
        "quantity": 1,
        "unit": 5,
        "total": 5
      },
      "corn": {
        "quantity": 5,
        "unit": 2,
        "total": 10
      }
    },
    "total": 24
  },
  "Edoka": {
    "invoice": {
      "potato": {
        "quantity": 3,
        "unit": 5,
        "total": 15
      },
      "onion": {
        "quantity": 1,
        "unit": 4,
        "total": 4
      },
      "corn": {
        "quantity": 5,
        "unit": 3,
        "total": 15
      }
    },
    "total": 34
  },
  "Were": {
    "invoice": {
      "potato": {
        "quantity": 3,
        "unit": 3,
        "total": 9
      },
      "onion": {
        "quantity": 1,
        "unit": 5,
        "total": 5
      },
      "corn": {
        "quantity": 5,
        "unit": 2,
        "total": 10
      }
    },
    "total": 24
  }
}

Answer 3

Я бы go для этого лично, это самая читаемая ИМО (хотя это, очевидно, субъективно). Я ожидаю, что производительность будет такой же хорошей, как и у всех, и это хороший шанс использовать довольно новый API Object.entries.

function cheapestStoreForRecipe(recipe, storeCollection){
    let cheapest, cheapestStore;
    for (const [storeName, store] of Object.entries(allStores)) {
        let total = 0;
        for (const [ingredient, amnt] of Object.entries(recipe)) {
            total += store[ingredient] * amnt;
        }

        if (!cheapest || total < cheapest) {
            cheapest = total;
            cheapestStore = storeName;
        }
    }

    return cheapestStore;
}

Answer 4

Это наиболее эффективный способ решения вашей проблемы:

function cheapestStoreForRecipe(recipe, storeCollection) {
    let cheapestStore;
    let cheapestPrice = Number.MAX_SAFE_INTEGER;

    Object.keys(storeCollection).forEach(store => {
        let costOfRecipe = 0;

        Object.keys(recipe).forEach(ingredient => {
            costOfRecipe += recipe[ingredient] || 0;
        });

        if (costOfRecipe < cheapestPrice) {
            cheapestPrice = costOfRecipe;
            cheapestStore = store;
        }
    });

    return cheapestStore;
}

Некоторые утверждают, что for более эффективен, чем forEach. Другие говорят, что это не так в современных условиях. Я предпочитаю реализацию forEach для удобства чтения.