Comments / Profile of brom

brom_portret@brom_portret^{read⁠-⁠only}

Пользователь

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 18:45

или например вот так тоже неплохо

function fv4o(a, x) {
    let result = -1;
    let end = (a || []).length;
    let start = 0;
    let pos = end >> 1;

    while (pos < end && result != x) {
        if (a[pos] > x) {
            end = pos;
            pos = ((end - start) >> 1) + start;
            continue;
        }

        result = a[pos];
        start = pos;
        pos = ((end - start) >> 1 || 1) + start;
    }

    return result;
}

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 17:30

ок, таки нашел время и сделал версию которая меня вроде устраивает, но еще можно поработать и оптимизировать

function fv4o(a, x) {
    if (a == null || a.length == 0) {
        return -1;
    }

    let result = -1;
    let end = a.length;
    let start = 0;
    let pos = end >> 1; // Relative position
    let abspos = pos; // Absolute position
    let item = 0;

    while (abspos < end) {
        item = a[abspos];

        if (item == x) {
            return x;
        }

        if (item <= x) {
            result = item;
            start = abspos;
        } else {
            end = abspos;
        }

        pos = (end - start) >> 1 || 1;
        abspos = pos + start;
    }

    return result;
}

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 17:22

Вот вам мой допиленный вариант:

function fv4o(a, x) {
    if (a == null || a.length == 0) {
        return -1;
    }

    let result = -1;
    let end = a.length;
    let start = 0;
    let relpos = end >> 1; // Relative cursor position from start
    let abspos = relpos;   // Absolute cursor position
    let item;

    while (abspos < end) {
        item = a[abspos];

        if (item == x) {
            return x;
        }

        if (item <= x) {
            result = item;
            start = abspos;
        } else {
            end = abspos;
        }

        relpos = (end - start) >> 1 || 1;
        abspos = relpos + start;
    }

    return result;
}

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 16:51

и вообще разве отбивки это основное? Там блин var!!! и Math.floor!!!. Этого уже достаточно кмк

-1

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 16:38

и на этом основании вы выше посоветовали не использовать let вместо var?

-1

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 16:33

а вот это действительно печально.

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 16:26

я пока не опубликовал финальное решение. то что в посте указано то что входной параметр массив или null я не заметил, это довольно странное условие в случае js. Но кстати его код проверяет еще и на undefined не очевидным образом, чего не было в условиях задачи. По поводу libc я не скажу что это хороший код, там много трэша. Вот посморите на getaddrinfo, https://codebrowser.dev/glibc/glibc/sysdeps/posix/getaddrinfo.c.html, разве это похоже на хороший код? Но даже там условия и циклы часто отбиты.

По поводу

if (foo ) {
}
явные начало и конец блока лучше чем не явные, читать проще и меньше ошибок в итоге

А теперь сравните с кодом из скажем ZFS https://github.com/openzfs/zfs/blob/master/module/avl/avl.c

По поводу кода предложенного автором - там вообще нет ни одной отбивки, все единым блоком кода. То есть явные проблемы с читаемостью. Даже в ваших примерах из glibc есть отбивки

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 15:55

понял о чем вы, действительно там есть лишние итерации

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 15:24

хорошо, я немного переделал бенчмарк чтобы он работал быстрее и надежнее добавил еще один вариант. Таки получается что var всегда медленнее чем let:

// Orignal version but with bits shift
function fv0(a, x) {
  if (a == null || a.length == 0) return -1;
  var answer = -1;
  var low = 0;
  var high = a.length - 1;

  while(low <= high) {
    var mid = (low + high) >> 1;
    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return answer;
}

// Let's user let instead of var
function fv1(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1

  while(low <= high) {
    let mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// Let's declare mid outside of loop
function fv2(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1
  let mid;

  while(low <= high) {
    mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}


// Let's declare mid outside of loop and initialize it
function fv3(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1
  let mid = 0;

  while(low <= high) {
    mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// My version
function fv4(a, x) {
    if (a == null || a.length == 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
        } else if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            return result;
        }
    }

    return result;
}

// Let's test
let a = [];
let t0 = 0;
let t1 = 0;
let t2 = 0;
let t3 = 0;
let t4 = 0;

let startTime;
let endTime;

for (j = 0; j < 4096; j++) {
    a[j] = Math.round(Math.random() * 1000);
}

a.sort((a, b) => {
    if (a < b) {
        return -1;
    }

    if (a > b) {
        return 1;
    }

    return 0;
})

for (let i = 0; i < 100000000; i++) {
    let x = Math.round(Math.random() * 1000);

    startTime = Date.now();
    let r0 = fv0(a, x);
    endTime = Date.now();
    t0 += (endTime - startTime);

    startTime = Date.now();
    let r1 = fv1(a, x);
    endTime = Date.now();
    t1 += (endTime - startTime);

    startTime = Date.now();
    let r2 = fv2(a, x);
    endTime = Date.now();
    t2 += (endTime - startTime);

    startTime = Date.now();
    let r3 = fv3(a, x);
    endTime = Date.now();
    t3 += (endTime - startTime);

    startTime = Date.now();
    let r4 = fv4(a, x);
    endTime = Date.now();
    t4 += (endTime - startTime);

    if (r4 != r0) {
        console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r4);
    }
}

console.log("original version", t0);
console.log("original version with let", t1);
console.log("original version with declared mid outside of the loop", t2);
console.log("original version with declared and initizalized mid outside of the loop", t3);
console.log("my version", t4);

node 1.js && node 1.js && node 1.js && node 1.js && node 1.js
original version 6730
original version with let 6398
original version with declared mid outside of the loop 6236
original version with declared and initizalized mid outside of the loop 6704
my version 7701
original version 6846
original version with let 6405
original version with declared mid outside of the loop 6326
original version with declared and initizalized mid outside of the loop 6493
my version 7682
original version 7000
original version with let 6448
original version with declared mid outside of the loop 6250
original version with declared and initizalized mid outside of the loop 6497
my version 7528
original version 6988
original version with let 6422
original version with declared mid outside of the loop 6395
original version with declared and initizalized mid outside of the loop 6508
my version 7566
original version 6887
original version with let 6373
original version with declared mid outside of the loop 6310
original version with declared and initizalized mid outside of the loop 6608
my version 7677

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 15:04

Если я правильно понял, то это касается только не инициализованных значений объявленных с помощью let?

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 14:59

мне кажется вы ошибаетесь, посмотрите пожалуйста вот этот мой коммент https://habr.com/ru/companies/ispsystem/articles/779224/comments/#comment_26245396 - я там в сравниваю результаты на рандомных данных с результатами оригинального алгоритма предложенного автором, расхождений в результатах функции не выявляется

Если вы считаете что алгоритм таки неверный, предложите тесткейс который это докажет. Если все так как вы говорите, это должно быть легко

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 14:26

немножко переделал свой код:

function fv3(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
        } else if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            return result;
        }
    }

    return result;
}

и прогнал 2000000 итераций для строки размером 2000, в этот раз версия с let внутри цикла, как ни странно, оказалась быстрее всех, первая версия которая приходит в голову это особенности GC

original version 143
original version with let 116
original version with declared mid outside of the loop 123
my version 120

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 14:09

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

// Orignal version but with bits shift
function fv0(a, x) {
  if (a == null || a.length == 0) return -1;
  var answer = -1;
  var low = 0;
  var high = a.length - 1;

  while(low <= high) {
    var mid = (low + high) >> 1;
    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return answer;
}

// Let's use let instead of var
function fv1(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1

  while(low <= high) {
    let mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// Let's declare mid outside of loop
function fv2(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1
  let mid;

  while(low <= high) {
    mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// My version
function fv3(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
            continue;
        }

        if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            break;
        }

    }

    return result;
}

// Let's test
let a = [];
let t0 = 0;
let t1 = 0;
let t2 = 0;
let t3 = 0;

for (let i = 0; i < 1000000; i++) {
    for (j = 0; j < 1000; j++) {
        a[j] = Math.round(Math.random() * 100);
    }

    a.sort((a, b) => {
        if (a < b) {
            return -1;
        }

        if (a > b) {
            return 1;
        }

        return 0;
    })

    let x = Math.round(Math.random() * 100);

    let startTime = Date.now();
    let r0 = fv0(a, x);
    let endTime = Date.now();
    t0 += (endTime - startTime);

    startTime = Date.now();
    let r1 = fv1(a, x);
    endTime = Date.now();
    t1 += (endTime - startTime);

    startTime = Date.now();
    let r2 = fv2(a, x);
    endTime = Date.now();
    t2 += (endTime - startTime);

    startTime = Date.now();
    let r3 = fv3(a, x);
    endTime = Date.now();
    t3 += (endTime - startTime);

    if (r3 != r0) {
        console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r3);
    }
}

console.log("original version", t0);
console.log("original version with let", t1);
console.log("original version with declared mid outside of the loop", t2);
console.log("my version", t3);


OUTPUT:
original version 83
original version with let 71
original version with declared mid outside of the loop 52
my version 61

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 13:41

я сейчас потестировал код предложенный автором на node v14 которая была под рукой. Так вот, если заменить var на let, он работает быстрее.

что касается бинарного поиска, то вот вам мой вариант, он медленнее чем код автора, но наверное если потратить чуть больше времени, можно сделать его быстрее

function find(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
            continue;
        }

        if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            break;
        }

    }

    return result;
}

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 13:34

и получилось бы в итоге у меня что-то типа такого:

function find(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += (len - pos) >> 1 || 1;
            continue;
        }

        if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            break;
        }

    }

    return result;
}

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 13:07

ну этого не было в условиях задачи. проверять что массив отсортирован дорого. А вот то что условиями покрыта только часть возможных неправильных аргументов это минус, где гарантия что этот чел не напишет такого в реальном проекте?

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 12:58

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

Если бы я дальше работал бы над кодом то разумеется получился бы бинарый поиск

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 12:33

я думал мы обсуждаем почему не стоит использовать var, поскольку вы написали "А вот если бы использовали var - такого вопроса бы не стояло."

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 12:19

нормальный человек использует другую переменную, потому что ошибка максимальна ясна и понятна.
про других я не скажу, может быть всякое.
А вот кейс с var плох тем что var x = something; может назначаться не всегда, а быть еще и завернута в if, который срабатывает только при каких-то редких обстоятельствах, так что код с ошибкой пройдет и ручное тестирование, и автотесты если они не покрывают тот самый редкий if и выстрелит у вас в продакшине. Лично подтверждаю что видел не один такой случай.

Моя любимая задачка по программированию для кодинг-интервью

@brom_portret Dec 8 2023 at 12:09

function bar() {
    let x = 1;
    const arr = [1, 2, 3, 4, 5];

    let x;
    for (let i = 0; i < 5; i++) {
       x = arr[i];
    }

    console.log(x);
}

$ node 1.js
  1.js:5
    let x;
        ^

SyntaxError: Identifier 'x' has already been declared

т.е. не получится допустить баг, будет показана явная ошибка при запуске, что я и имел в виду

1 2 3

5 6 ...

11 12