void add(int x) {
b.push_back(x);
if (sqr(size(b)) >= size(a)) {
a += b;
sort(a);
b = vector<int>();
}
}
Сортировка после конкатенации здесь - это так себе затея по-моему. Если бОльший массив уже отсортирован - это почти готовый Merge Sort, осталось отсортировать меньший и смёржить. Но за псевдокод сойдёт.
Почитал про fair share здесь, интересно, спасибо за наводку. В среднем наверно да, это более соответствует пользовательскому ожиданию. Если пользователь не бухгалтер, которому надо срочно посчитать и закрыть день, а маректолог со своими анализами кликов подождёт. Отдельному пользователю можно подкрутить ресурс? Чтоб не орала на весь офис: срочно выйдете все из базы! А то останетесь без зарплаты.
Попробую придумать какой-нибудь пример. Есть клиенты (конечные UI, узлы в цепочке вычислений, сервисы и пр.). Каждый клиент делает запрос на большой объём данных, а критично ему сразу получить, скажем, первые 100 строк (или там, пачек). Обращение за каждой очередной порцией данных помещается в очередь, откуда их должен достать процесс из тредпула и обработать, как вариант: 1) Продолжить выполнение SQL 2) Достать уже посчитанный ответ из кеша в ОЗУ 3) Достать ответ из временного хранилища данных сессии на диске ... и вернуть очередную порцию клиенту. Кроме таких запросов на порции данных, в очередь попадают более критичные вычислительные задачи. Если мы немного диградируем, возможно даже на уровне сокетов, ту часть системы, которая принимает реквесты на получение 101-й и далее некритичных порций данных, разве мы не увеличим таким образом эффективность тредпула в части обработки более полезных задач? Но даже не об этом. Допустим, у нас нет других вычислений, остались только запросы на порции данных и их очень много. Если часть из них они сразу забьёт очередь, тогда остальным придётся сделать отказ. Клиент, который ещё возится с первой сотней строк, очень расстроиться, что ему прилетел отлуп. Если же растянуть поступление в очередь во времени, превратить в ленивцев на стороне СУБД, то у процессов из тредпула появляется больше шансов успеть справиться с нагрузкой без переполнения очередей и соответственно необходимости отказа. Да, может наступить момент, когда уже и это не поможет, но... это так, на подумать.
Снизу — overload controller. Этот блок собирает feedback в виде размеров очередей тредпулов и отправляет сигнал контроля для RPC: принимать или отклонять запросы.
Пока очереди не заполнились до критической отметки, но статистика уже распологает, возможно, контролеру есть смысл ещё и замедлять запросы? Вставлять какие-то примлемые паузы между реквестами, чтоб дать больше времени очередям для освободиться.
arrPersons.rowIdx даже не нужен, строка откуда пришли уже и так известна, а если запись удалена, то элемент arrChangedPersons будет содержать пустой список null. Ну и ещё м.б. отдельный массив для заинсерченных в пишушей сессии записей arrInsertedPersons, с проходом по нему после основного массива arrPersons. Если нужен частичный откат транзакции до точки останова, то надо сохранять всю историю изменений, будет чуть сложнее
Ещё раз попробую. Будет не перебор второго массива, а прямой доступ к элементу этого массива, сложность O(1). Например, основная таблица Persons (ID, Name, Age) представлена как массив arrPersons[rowIdx][colIdx], но с дополнительным 4-м полем ChangeIdx:
Если сессия читающая, то поле ChangeIdx игнорируется. Если сесси пишущая, а в вашей СУБД она всего одна для таблицы, то во время прохода смотрим: У записей с айди 100 и 300 ChangeIdx = null, значит они не модифицировались, считываем данные как есть.
У записи 200 ChangeIdx = 0 значит в массиве изменений arrChangedPersons[ChangeIdx] по индексу 0 для него есть изменённая запись, например, с новым возрастом
arrChangedPersons[0] = 200, "Петров", 55 Петров повзрослел на год. Всё, просто забираем эту новую запись из arrChangedPersons без всяких проходов.
Дальше можно подумать, как не дублировать в arrChangedPersons данные которые не изменились, а писать туда только изменения. Допустим, у записи 200 поменялся и возраст, и фамилия - Петров стал 56-летним Петровским. Может тогда в arrChangedPersons[0] помещать односвязный список записей с полями:
arrPersons.rowIdx // индекс строки основного массива arrPersons.colIdx // индекс столбца основного массива newValue // новое значение, допустим, "Петровский" nextPointer // указатель на следующее изменённое значение записи таблицы, относящеесе уже к возрасту 200-го ... и т.д.
Вся таблица в виде массива в RAM когда-нибудь порвёт RAM, но да ладно. Чтоб не делать вложенные проходы, можно докинуть изменяемое служебное поле для каждой ридонли-записи в основном массиве. В этом поле хранить индекс изменённой версии записи во втором массиве. При проходе проверка: нет индекса - не было изменений, есть - берём данные по индексу.
Да, интересно, продолжайте. Неплохо бы, например, подробнее про формат страницы. Там же ещё где-то инфа о полях таблицы должна быть, их типах. Что если размер записи превышает размер страницы и занимает, скажем 2.5, а не одну. Или запись не имеет фиксированной длины, поскольку содержит текстовые поля неограниченного размера, причем так, что сам текст может занимать больше одной странцы. Есть ли вообще смысл размещать большой текст постранично? Кроме самих данных и ссылки на следующую странцу, какую метаинформацию страница ещё должна содержать? И т.д., и т.п.
Как вариант, накопленная энергия, которую постоянно сдерживали, и раздражение с этим связаное, найдет выход по окончании школы, когда бывший ученик прийдёт и всех постреляет.
Плохое настроение 3 дня подряд у ребенка будет от того, что садисты снимают его на камеру и пытаются сделать обездвиженное растение. Как эту проблему будут решать психологи? Ведь если подопытный станет весёлым, он снова побежит.
Примерно понял. Интересно про Redux с т.з. пользы и вреда. На счет того, что он дает удобство сопровождения понятно. А стор же отжирает память? Есть, скажем, таблица транзакций слева в 100 000 записей под гиг, которую хочет быстро проскролить аудитор, а справа форма с данными по выделенной транзакции. Если данные из выделенной строки перекидывать в форму не напрямую, а через стор, он же будет содержать дубликаты данных, которые уже находится в DOM-объекте HTMLTableElement.table.rows, да? Т.е. памяти страница отожрет в 2 раза больше как минимум. Еще наверняка есть какие-то обертки для каждой строки, которые слушают изменения в сторе, если данные транзакции поменялась из формы. Плюс журналируются изменные стэйты — еще минус память. Или все не так плохо с этой технологией, как кажется? Ну это так :)
Я конечно извиняюсь, что высказываю впечатление, случайно зайдя в тему, не являясь реакт- разработчиком, но если фреймворк приходится использовать с такой гигантской инвалидной каляской, вы уверены, что это вообще можно называть фреймворком?
Если внимательно посмотреть на фото с Анжелой Арендс, то станет понятно, почему она ушла после выхода iPhone X. В отличае от нового руковолителя Дейдры О'Брайен, Анжела терпеть не может дурацкие челки.
Но жестко блокированное, скорее всего, быстренько всплывет в форме голосового голюциноза. Т.е. срок эксплуатации такого «зомбика» будет не очень длинный. Но уродов это вряд ли остановит. Кто-то не из глупых сказал, что бог создал всех людей веселыми и счастливыми — пока они не начали лезть в настройки )))
To shrink — это действие с самим стеком (массивом).
Т.е. в js — добавление\удаление элемента в начало массива — shift \ unshift (сдвиг), означают действие над массивом. А добавление\удаление с конца — push \ pop — это относится к элементу. Ну как-то… Хотя в первом случае он действительно сдвигается. А в случае pop не только урезается массив, но и возвращается верхнее значение, подобно пуле, выстреленной из магазина. Вобщем, спасибо, парни, теперь я точно не забуду, что делают эти методы, татуровку делать не придется ))
Вот тоже самое хотел сказать про pop и push — если знать значения этих слов, то и порнография не нужна никакая.
А вот интересно. Как знание того, что «to pop» переводится, как хлопать, поможет понять, что это удаление с конца массива, без представление этого слова в порнографическом контексте? Почему не какой-нибудь shrink или prune. А какое отношении «push» (проталкивать, продвигать) имеет к добавлению в конец массива? Если б в начало еще ладно — силком втолкнули элемент в начало, остальной массив продивнулся… Так нет, не add, не append, а опять какая-то порнография. Не язык, а изврат какой-то )
По модифицированному
адду в пополняемом массивеСортировка после конкатенации здесь - это так себе затея по-моему. Если бОльший массив уже отсортирован - это почти готовый Merge Sort, осталось отсортировать меньший и смёржить. Но за псевдокод сойдёт.
Почитал про fair share здесь, интересно, спасибо за наводку. В среднем наверно да, это более соответствует пользовательскому ожиданию. Если пользователь не бухгалтер, которому надо срочно посчитать и закрыть день, а маректолог со своими анализами кликов подождёт. Отдельному пользователю можно подкрутить ресурс? Чтоб не орала на весь офис: срочно выйдете все из базы! А то останетесь без зарплаты.
Попробую придумать какой-нибудь пример. Есть клиенты (конечные UI, узлы в цепочке вычислений, сервисы и пр.). Каждый клиент делает запрос на большой объём данных, а критично ему сразу получить, скажем, первые 100 строк (или там, пачек). Обращение за каждой очередной порцией данных помещается в очередь, откуда их должен достать процесс из тредпула и обработать, как вариант:
1) Продолжить выполнение SQL
2) Достать уже посчитанный ответ из кеша в ОЗУ
3) Достать ответ из временного хранилища данных сессии на диске
... и вернуть очередную порцию клиенту.
Кроме таких запросов на порции данных, в очередь попадают более критичные вычислительные задачи. Если мы немного диградируем, возможно даже на уровне сокетов, ту часть системы, которая принимает реквесты на получение 101-й и далее некритичных порций данных, разве мы не увеличим таким образом эффективность тредпула в части обработки более полезных задач? Но даже не об этом. Допустим, у нас нет других вычислений, остались только запросы на порции данных и их очень много. Если часть из них они сразу забьёт очередь, тогда остальным придётся сделать отказ. Клиент, который ещё возится с первой сотней строк, очень расстроиться, что ему прилетел отлуп. Если же растянуть поступление в очередь во времени, превратить в ленивцев на стороне СУБД, то у процессов из тредпула появляется больше шансов успеть справиться с нагрузкой без переполнения очередей и соответственно необходимости отказа. Да, может наступить момент, когда уже и это не поможет, но... это так, на подумать.
Пока очереди не заполнились до критической отметки, но статистика уже распологает, возможно, контролеру есть смысл ещё и замедлять запросы? Вставлять какие-то примлемые паузы между реквестами, чтоб дать больше времени очередям для освободиться.
arrPersons.rowIdx даже не нужен, строка откуда пришли уже и так известна, а если запись удалена, то элемент arrChangedPersons будет содержать пустой список null. Ну и ещё м.б. отдельный массив для заинсерченных в пишушей сессии записей arrInsertedPersons, с проходом по нему после основного массива arrPersons. Если нужен частичный откат транзакции до точки останова, то надо сохранять всю историю изменений, будет чуть сложнее
Ещё раз попробую. Будет не перебор второго массива, а прямой доступ к элементу этого массива, сложность O(1). Например, основная таблица Persons (ID, Name, Age) представлена как массив arrPersons[rowIdx][colIdx], но с дополнительным 4-м полем ChangeIdx:
100, "Иванов", 23, null
200, "Петров", 54, 0
300, "Бобров", 37, null
Если сессия читающая, то поле ChangeIdx игнорируется.
Если сесси пишущая, а в вашей СУБД она всего одна для таблицы, то во время прохода смотрим:
У записей с айди 100 и 300 ChangeIdx = null, значит они не модифицировались, считываем данные как есть.
У записи 200 ChangeIdx = 0 значит в массиве изменений arrChangedPersons[ChangeIdx] по индексу 0 для него есть изменённая запись, например, с новым возрастом
arrChangedPersons[0] = 200, "Петров", 55
Петров повзрослел на год. Всё, просто забираем эту новую запись из arrChangedPersons без всяких проходов.
Дальше можно подумать, как не дублировать в arrChangedPersons данные которые не изменились, а писать туда только изменения. Допустим, у записи 200 поменялся и возраст, и фамилия - Петров стал 56-летним Петровским. Может тогда в arrChangedPersons[0] помещать односвязный список записей с полями:
arrPersons.rowIdx // индекс строки основного массива
arrPersons.colIdx // индекс столбца основного массива
newValue // новое значение, допустим, "Петровский"
nextPointer // указатель на следующее изменённое значение записи таблицы, относящеесе уже к возрасту 200-го
...
и т.д.
Вся таблица в виде массива в RAM когда-нибудь порвёт RAM, но да ладно. Чтоб не делать вложенные проходы, можно докинуть изменяемое служебное поле для каждой ридонли-записи в основном массиве. В этом поле хранить индекс изменённой версии записи во втором массиве. При проходе проверка: нет индекса - не было изменений, есть - берём данные по индексу.
Да, интересно, продолжайте. Неплохо бы, например, подробнее про формат страницы. Там же ещё где-то инфа о полях таблицы должна быть, их типах. Что если размер записи превышает размер страницы и занимает, скажем 2.5, а не одну. Или запись не имеет фиксированной длины, поскольку содержит текстовые поля неограниченного размера, причем так, что сам текст может занимать больше одной странцы. Есть ли вообще смысл размещать большой текст постранично? Кроме самих данных и ссылки на следующую странцу, какую метаинформацию страница ещё должна содержать? И т.д., и т.п.
Как вариант, накопленная энергия, которую постоянно сдерживали, и раздражение с этим связаное, найдет выход по окончании школы, когда бывший ученик прийдёт и всех постреляет.
Плохое настроение 3 дня подряд у ребенка будет от того, что садисты снимают его на камеру и пытаются сделать обездвиженное растение. Как эту проблему будут решать психологи? Ведь если подопытный станет весёлым, он снова побежит.
www.youtube.com/watch?v=YMFgjuNWYgo
Т.е. в js — добавление\удаление элемента в начало массива — shift \ unshift (сдвиг), означают действие над массивом. А добавление\удаление с конца — push \ pop — это относится к элементу. Ну как-то… Хотя в первом случае он действительно сдвигается. А в случае pop не только урезается массив, но и возвращается верхнее значение, подобно пуле, выстреленной из магазина. Вобщем, спасибо, парни, теперь я точно не забуду, что делают эти методы, татуровку делать не придется ))
Поэтому и спрашиваю у знаков английского
to pop
хлопнуть — отмечено как употребляемое в этом значении чаще остальных
хлопать
палить — это что ли? типа сжечь элемент массива? ))) а почему не стандартные del или remove. В названии что-то указывает на последнесть элемента?
трескаться
выстреливать
поджаривать кукурузные зерна
стрелять
бросаться
возникнуть
внезапно спросить
огорошить вопросом
закладывать
принимать
короче, бред какой-то,
без костылей в виде ассоциаций, запомнить, что делает метод будет не просто
А вот интересно. Как знание того, что «to pop» переводится, как хлопать, поможет понять, что это удаление с конца массива, без представление этого слова в порнографическом контексте? Почему не какой-нибудь shrink или prune. А какое отношении «push» (проталкивать, продвигать) имеет к добавлению в конец массива? Если б в начало еще ладно — силком втолкнули элемент в начало, остальной массив продивнулся… Так нет, не add, не append, а опять какая-то порнография. Не язык, а изврат какой-то )