ты можешь найти вызов Вот подробности, но тема говорит сама за себя;
Проверьте предоставленный список записей на 2 числа, которые в сумме составляют 2020, верните произведение этих добавлений.
Я дождался окончания мероприятия, чтобы все было по-честному.
/*This will search for 2 numbers in the `list that sum to `target`
Assumption;
* We only get integers in a string that are new-line separated
* The sum is there, so we dont stop searching even if it doesnt make sense
*/
function findTargetSum(listAsString, target){
const list = entries.split('n').map(s => s*1);
const set = new Set(list);
for (const i of set) {
if(set.has(target - i)){
return i * (target - i);
}
}
}
function findTargetSum3(listAsString, target){
const list = entries.split('n').map(s => s*1);
const set = new Set(list);
for (const i of set){
for(const i2 of set){
if(i != i2){
if(set.has(target -i - i2)){
return i * i2 * (target -i - i2);
}
}
}
}
}
const entries = `1780
1693
1830
1756
1858
1868
1968
1809
1996
1962
1800
1974
1805
1795
170
1684
1659
1713
1848
1749
1717
1734
956
1782
1834
1785
1786
1994
1652
1669
1812
1954
1984
1665
1987
1562
2004
2010
1551
961
1854
2005
1883
1965
475
1776
1791
262
1912
1227
1486
1989
1857
825
1683
1991
1875
1982
1654
1767
1673
1973
1886
1731
1745
1770
1995
1721
1662
1679
1783
1999
1889
1746
1902
2003
1698
1794
1798
1951
1953
2007
1899
1658
1705
62
1819
1708
1666
2006
1763
1732
1613
1841
1747
1489
1845
2008
1885
2002
1735
1656
1771
1950
1704
1737
1748
1759
1802
2000
1955
1738
1761
1765
1853
1900
1709
1979
1911
1775
1813
1949
1966
1774
1977
1757
1992
2009
1956
1840
1988
1985
1993
1718
1976
1078
1997
1897
1792
1790
1801
1871
1727
1700
1485
942
1686
1859
1676
802
1952
1998
1961
1844
1808
1703
1980
1766
1963
1849
1670
1716
1957
1660
1816
1762
1829
526
359
2001
1874
1778
1873
1511
1810
1699
1970
1690
1978
1892
1691
1781
1777
1975
1967
1694
1969
1959
1910
1826
1672
1655
1839
1986
1872
1983
1981
1972
1772
1760`;
console.log(findTargetSum(entries, 2020));
console.log(findTargetSum3(entries, 2020)); 2 ответа
Выглядит в основном нормально, хотя есть несколько проблем:
Ошибка аргумента / опечатка Вы имеете в виду переменную верхнего уровня entries внутри функции вместо listAsString аргумент.
Совпадение чисел? Даже если сказано, что ввод будет содержать числа, разделенные строками, я бы предпочел сопоставление числовых символов вместо разделения по новой строке. Он будет более надежным, если входные данные будут отформатированы неправильно, или как минимум делает намерение (извлечь из входных данных массив, состоящий только из цифр) немного яснее, не полагаясь на описание.
Может быть, использовать Number? Когда у вас есть массив цифровых символов, вы превращаете их все в числа с помощью .map(s => s*1). Я думаю, что цель — преобразовать числа — было бы немного яснее, если бы .map(Number) вместо.
я обычно используется для обозначения индекс повторяется. Вот, i не используется как индекс, а как элемент повторяется. Может быть, использовать num вместо?
target - i можно сохранить в переменной вместо того, чтобы повторять ее дважды, если хотите.
Ошибка подсчета Если целевая сумма оказывается суммой двух такое же количество, например: 1010 + 1010, они будут сопоставлены, даже если входные данные содержат только одно из этих чисел, поскольку вы используете Set, который не отличает одно вхождение от нескольких.
Чтобы исправить это, вы можете добавить проверку индекса к исходному массиву, если два числа совпадают (как я сделал ниже), или подсчитать количество вхождений в объект, или что-то в этом роде.
С участием findTargetSum3, в дополнение к вышесказанному:
Вычислительная сложность излишне велика Первый подход O(n), и это хорошо. Этот второй подход O(n ^ 2), поскольку вы проверяете каждый элемент против любого другого элемента. Я бы бросил findTargetSum3 полностью.
Предпочитаю строгое равенство над свободным равенством — да, типы точно такие же, поэтому это не имеет значения в логике, но строгое равенство с !== и === легче понять с первого взгляда из-за отсутствия странные правила принуждения. Всякий раз, когда я вижу неаккуратное сравнение (особенно в профессиональном коде), я думаю: «Почему не используется строгое сравнение, есть ли какие-то возможные странности приведения типов, которые не были явными?» Лучше быть последовательным и везде использовать строгое сравнение на равенство.
function findTargetSum(listAsString, target){
const numbers = listAsString.match(/d+/g).map(Number);
const set = new Set(numbers);
for (const num of set) {
const otherNum = target - num;
if (
set.has(otherNum) &&
(num !== otherNum || numbers.indexOf(num) !== numbers.lastIndexOf(otherNum))
) {
return num * otherNum;
}
}
}
const entries = `1780
1693
1830
1756
1858
1868
1968
1809
1996
1962
1800
1974
1805
1795
170
1684
1659
1713
1848
1749
1717
1734
956
1782
1834
1785
1786
1994
1652
1669
1812
1954
1984
1665
1987
1562
2004
2010
1551
961
1854
2005
1883
1965
475
1776
1791
262
1912
1227
1486
1989
1857
825
1683
1991
1875
1982
1654
1767
1673
1973
1886
1731
1745
1770
1995
1721
1662
1679
1783
1999
1889
1746
1902
2003
1698
1794
1798
1951
1953
2007
1899
1658
1705
62
1819
1708
1666
2006
1763
1732
1613
1841
1747
1489
1845
2008
1885
2002
1735
1656
1771
1950
1704
1737
1748
1759
1802
2000
1955
1738
1761
1765
1853
1900
1709
1979
1911
1775
1813
1949
1966
1774
1977
1757
1992
2009
1956
1840
1988
1985
1993
1718
1976
1078
1997
1897
1792
1790
1801
1871
1727
1700
1485
942
1686
1859
1676
802
1952
1998
1961
1844
1808
1703
1980
1766
1963
1849
1670
1716
1957
1660
1816
1762
1829
526
359
2001
1874
1778
1873
1511
1810
1699
1970
1690
1978
1892
1691
1781
1777
1975
1967
1694
1969
1959
1910
1826
1672
1655
1839
1986
1872
1983
1981
1972
1772
1760`;
console.log(findTargetSum(entries, 2020));
console.log(findTargetSum(`1
3
3
5`, 6));Ошибки
Есть 3 ошибки или две в зависимости от ввода.
Обе функции используют неопределенную переменную.
entriesкоторый должен быть либоlistAsStringили измените аргументlistAsStringкentriesВторая функция не возвращает правильные значения. Эту функцию вообще не стоит рассматривать, потому что вы повторяете набор для каждого элемента в наборе. Наборы используют сгенерированные хеш-ключи для поиска элементов, они устраняют необходимость выполнять этот тип поиска.
Будет ли 1010 отображаться один в списке ввода?
Если да, то ваш код не работает, так как может вернуть
1010 * 1010 === 1020100потому что ваш поиск найдет совпадениеset.has(target - i).Если нет, то это не ошибка.
Обзор
Поскольку ваш вопрос отмечен «программирование» этот обзор посвящен производительности,
Проблемы программирования
Основная цель сайтов с задачами программирования — предоставить задачи для получения опыта программирования. Задача состоит в том, чтобы выполнить задание и обеспечить правильный возврат. Таким образом, акцент делается не столько на том, как вы пишете код, сколько на том, что он делает.
Помимо правильного возвращаемого значения, эти сайты используют производительность для оценки кода. (Я не являюсь участником связанного сайта, поэтому неясно, верно ли это для этого сайта)
Не существует другой не субъективной метрики для оценки кода, кроме длины кода, и поскольку на сайте нет упоминания о кодовом гольф-коде, длина кода в этом обзоре не рассматривается.
Один предполагает, что, поскольку вы являетесь участником, вас интересует система рейтингов и получение лучших баллов за представленные материалы. Таким образом, в ваших решениях будет важна производительность.
Избегайте ненужной обработки
Нет необходимости создавать Set для всех номеров, прежде чем начинать тестирование каждого номера. Добавление числа к Set хотя и не сложный, это не быстро, так как есть накладные расходы, связанные с вычислением хэша.
То же самое и с преобразованием строки в число. Это также можно сделать во время итерации.
Число из строки
Есть много способов преобразовать строковое значение в число. Самый эффективный стандартный способ — использовать Number("1234"). Хотя есть особые случаи, когда это можно улучшить (см. Перепись 2).
Непонятно, какого типа target значение есть. Если это строка, вам необходимо убедиться, что вы преобразовали ее в число, прежде чем использовать ее внутри цикла. Использование его в качестве строки внутри цикла будет означать, что он преобразуется в число на каждой итерации, что является ненужными накладными расходами.
Лучший, средний и худший случаи
Перезапись (см. Ниже) настроена на производительность, чтобы гарантировать, что не будет случаев, когда производительность будет слишком сильно снижена, функции тестируются для лучших и худших наборов данных. Тогда окончательная оценка производительности производится на случайном наборе входных данных.
Средняя производительность. Если мы предположим, что строка чисел имеет два значения, вставленных случайным образом, а затем протестируем производительность на большом количестве этих случайных массивов, увеличение производительности перезаписи составит На 132% быстрее.
В наихудшем возможном случае (значения суммируются с 2020 как последние два элемента во входном списке) существенного прироста производительности не наблюдается.
В лучшем случае (значения — это первые 2 пункта в списке) улучшение огромно, разрушая на 5200% быстрее, чем ваш оригинал.
Если аргумент target представляет собой строку, и вы преобразуете ее в число один раз, прежде чем цикл будет сокращен еще на 5%.
Перепишите 1
Перезапись предполагает, что цель также является строкой.
В функциях нет необходимости в длинных именах. Размер области определяет размер имени переменной. Вот почему у нас есть возможности. При переписывании используются более короткие имена.
set никогда не бывает хорошим именем для Set назовите его тем, что он держит, а не тем, что он есть.
Rewrite предполагает, что 1010 может появиться в списке только один раз. Оптимизация добавления в набор values внутри цикла предотвратит ложное совпадение для одиночного 1010.
function findTargetSum(list, target){
list = list.split("n");
target = Number(target); // only if target is type string
const values = new Set();
for (const str of list) {
const num = Number(str), val = target - num;
if (set.has(val)) { return val * (target - val ) }
set.add(num);
}
}Есть более быстрый способ?
Да.
Javascript плохо справляется со строками. Назначение строки переменной требует, чтобы строка была скопирована, что, в отличие от объекта, которому просто нужна ссылка, скопированной строке также требуется итерация.
Линия for (const str of list) создает копию каждой строки. Этого можно избежать, фактически всего копирования строк можно избежать, декодируя числа с помощью String.charCodeAt
Принимая положительные значения только в списке, следующая функция: На 400% быстрее чем ваша первая функция в наборе случайных массивов, вторая функция, которая включает отрицательные значения, На 350% быстрее.
Перепишите 2
Это переписывание жестко сфокусировано на производительности. Избегает медленного string.split путем декодирования чисел по одному символу за раз. Каждый раз, когда он встречает новую строку (код символа 10), он проверяет декодированное число, выходит, если значения найдены, или продолжается.
Как только персонажи "0-9" и "n" ожидается, что функция может работать очень быстро.
В случайном наборе чисел с двумя значениями, вставленными случайным образом, следующая функция на 400% быстрее, чем ваш исходный код.
function test(list, target) {
var i = 0, num = 0;
const numbers = new Set();
while (i < list.length) {
const code = list.charCodeAt(i++) - 48;
if (code === -38) {
if (numbers.has(target - num)) { return num * (target - num) }
numbers.add(num);
num = list.charCodeAt(i++) - 48;
} else { num = num * 10 + code }
}
}Отрицательные
Входной набор может содержать отрицательные значения, некоторые числа будут иметь "-" (код 45), чтобы избежать лишних накладных расходов, тест на отрицательный результат необходимо проводить только один раз для каждого числа. Поскольку список не содержит новых строк в строке, мы знаем, что после новой строки стоит либо «-», либо цифра «0» — «9».
В качестве проверки на отрицательные элементы в тех частях кода, которые дают вышеуказанной функции преимущество в производительности, следующая функция для случайного набора чисел на 350% быстрее. Тем не менее значительное увеличение производительности.
function test(list, target) {
var i = 0, code = list.charCodeAt(i++);
var num = code === 45 ? -(list.charCodeAt(i++) - 48) : code - 48;
const numbers = new Set();
while (i < list.length) {
code = list.charCodeAt(i++) - 48;
if (code === -38) {
if (numbers.has(target - num)) { return num * (target - num) }
numbers.add(num);
code = list.charCodeAt(i++);
num = code === 45 ? -(list.charCodeAt(i++) - 48) : code - 48;
} else { num = num * 10 + code }
}
}Можно сделать отрицательный тест функцией, но это может снизить производительность, потому что встраивание функции произойдет только после того, как оптимизатор JS увидит, что функция запускается много раз. Для небольшого набора прогонов <~ 100 оптимизатор не сможет творить чудеса.
Включая константы, а не магические числа
функциональный тест (список, цель) {const CHAR_0 = 48, CHAR_NEWLINE_SUB_0 = -38, CHAR_NEG = 45; const startNumber = () => [
const code = list.charCodeAt(i++);
return code === CHAR_NEG ? -(list.charCodeAt(i++) - CHAR_0) : code - CHAR_0;
}
var i = 0, num = startNumber();
const numbers = new Set();
while (i < list.length) {
const code = list.charCodeAt(i++) - CHAR_0;
if (code === CHAR_NEWLINE_SUB_0 ) {
if (numbers.has(target - num)) { return num * (target - num) }
numbers.add(num);
num = startNumber();
} else { num = num * 10 + code }
}
}Notes
All code run on Chrome 87 Win x64.
Code used your original data as posted moving the matching values from top to bottom of list to determine best and worst cases.
The second rewrite used a similar input set of number (3 — 4) characters long. It is unclear what size ints the inputs could be. Performance for rewrite2 will be effected more by long numbers than the first (or your original)
The random data sets were created as follows. (two version on positive only values)
const SUM = 2020;
const LENGTH = 200;
const MIN = 900;
const MAX = 4000;
const POSITIVE = true;
function createTestData() {
const a = $setOf(LENGTH, () => $randI(MIN, MAX));
var find = true;
while (find) {
v = a[$randI(LENGTH)]; if (v Производительность имеет значение
В реальном мире производительность очень важна.
Циклы ЦП имеют свою цену.
Для серверного кода это буквальные затраты, мощность, инфраструктура.
Для клиентского кода он более тонкий, поскольку производительность приравнивается к качеству, низкокачественные приложения разряжают батареи и выглядят вялыми, что на конкурентном рынке снижает популярность и, в конечном итоге, приводит к потере клиентов.
Расходы клиента. Код, работающий на клиенте, будет использовать их мощность, сокращая время автономной работы и обходя им деньги. Код Perform-Ant - это продуманный код.
Социальная и этическая ответственность. Каждый цикл ЦП будет генерировать некоторое количество CO2, в совокупности даже небольшой прирост производительности может значительно снизить CO2 вывод. Увеличение срока службы устройства снижает количество отходов.