Быстрый ввод/вывод в конкурентном программировании

Я часто встречал этот фрагмент кода в решениях конкурсов конкурентного программирования. Я понимаю, что основное использование этого кода превзошло временные рамки, но я хочу понять его более глубоко. Я знаю, что unistd.h предоставляет доступ к функциям оболочки системного вызова, таким как примитивы fork, pipe и I/O (чтение, запись,..).

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

#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
class FastInput {
public:
 FastInput() {
 m_dataOffset = 0;
 m_dataSize = 0;
 m_v = 0x80000000;
 }
 ******** ReadNext() {
 if (m_dataOffset == m_dataSize) {
 int r = read(0, m_buffer, sizeof(m_buffer));
 if (r <= 0) return m_v;
 m_dataOffset = 0;
 m_dataSize = 0;
 int i = 0;
 if (m_buffer[0] < '0') {
 if (m_v != 0x80000000) {
 m_data[m_dataSize++] = m_v;
 m_v = 0x80000000;
 }
 for (; (i < r) && (m_buffer[i] < '0'); ++i);
 }
 for (; i < r;) {
 if (m_buffer[i] >= '0') {
 m_v = m_v * 10 + m_buffer[i] - 48;
 ++i;
 } else {
 m_data[m_dataSize++] = m_v;
 m_v = 0x80000000;
 for (i = i + 1; (i < r) && (m_buffer[i] < '0'); ++i);
 }
 }
 }
 return m_data[m_dataOffset++];
 }
public:
 ******* m_buffer[32768];
 ******** m_data[16384];
 size_t m_dataOffset, m_dataSize;
 ******** m_v;
};
class FastOutput {
public:
 FastOutput() {
 m_dataOffset = 0;
 }
 ~FastOutput() {
 }
 void Flush() {
 if (m_dataOffset) {
 if (write(1, m_data, m_dataOffset));
 m_dataOffset = 0;
 }
 }
 void *********(******** v, char d) {
 if (m_dataOffset + 11 > sizeof(m_data)) Flush();
 if (v < 100000) {
 if (v < 1000) {
 if (v < 10) {
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 1;
 } else if (v < 100) {
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 2;
 } else {
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 3;
 }
 } else {
 if (v < 10000) {
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 4;
 } else {
 m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 5;
 }
 }
 } else {
 if (v < 100000000) {
 if (v < 1000000) {
 m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 6;
 } else if (v < 10000000) {
 m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 7;
 } else {
 m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 8;
 }
 } else {
 if (v < 1000000000) {
 m_data[m_dataOffset + 8] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 9;
 } else {
 m_data[m_dataOffset + 9] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 8] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 7] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 6] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 5] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 4] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 3] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 2] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 1] = v - v / 10 * 10 + 48;
 v /= 10;
 m_data[m_dataOffset + 0] = v + 48;
 m_dataOffset += 10;
 }
 }
 }
 m_data[m_dataOffset++] = d;
 }
 void PrintChar(char d) {
 if (m_dataOffset + 1 > sizeof(m_data)) Flush();
 m_data[m_dataOffset++] = d;
 }
 void ReplaceChar(int offset, char d) {
 m_data[m_dataOffset + offset] = d;
 }
public:
 ******* m_data[32768];
 size_t m_dataOffset;
};
</unistd.h></stdint.h></stdlib.h>

Еще одна вещь: хорошо ли использовать аналогичные методы в коде уровня производства?

3 ответа

Хорошо ли использовать аналогичные методы в коде уровня производства?

Нет. Повторное использование колеса приводит к ошибкам. Ошибки требуют дополнительного времени разработки и затрат.

может помочь мне понять это дальше.

Если вы не понимаете код, код плохо написан. Код написан людьми, а также людьми. Если другой программист не понимает код быстро, может возникнуть большая проблема. Обоснование этого мышления ( "написанное для людей" ) прост: время разработки стоит много, а нечитаемый код увеличивает время разработки.

В данном фрагменте кода используется несколько неправильных методов кодирования:

  • Венгерская нотация (нет необходимости в этом случае с учетом регистра и особенно на С++),
  • Короткие члены переменной (можете ли вы сказать, что означает m_v без чтения остальной части программы, например?)
  • Жестко-кодированные значения (+ 48, + 11)
  • (субъективный) Смешивание подписанных /unsigned ints/chars (mingw/gcc будет раздражать вас от коммита при компиляции).
  • Скопировать код в скобки (v /= 10 и аналогичный - С++ имеет макросы/шаблоны, черт возьми, поэтому, если вы хотите развернуть цикл вручную, используйте их!).
  • Необязательно многоуровневое if/else.

Если вы не хотите ухудшаться при программировании, я бы посоветовал не пытаться "понять" этот фрагмент кода. Это плохо.

Я серьезно сомневаюсь, что этот конкретный дизайн был результатом профилирования. Скорее всего, какой-то "гений" предположил, что его фрагмент кода превзойдет встроенные функции.

Если вам нужна производительность, вы следуете этому шаблону:

  • Записать исходную версию.
  • Повторяйте до тех пор, пока усиление производительности больше не стоит или пока не будет найдено решение:
    • Не делайте много предположений о том, что улучшит производительность. Вы - человеческая, человеческая задача - совершать ошибки. По закону Мерфи ваши предположения будут неверными.
    • Сначала рассмотрим алгоритмическую оптимизацию.
    • Запустите код через профайлер.
    • Найдите узкие места.
    • Исследуйте общее увеличение производительности, если общее время, затрачиваемое на эту конкретную процедуру, будет уменьшено до нуля.
    • Если коэффициент усиления является разумным (время/стоимость), оптимизируйте процедуру. В противном случае игнорируйте.


В функции ********* он в основном просто разворачивает петлю вручную. Иногда прокручивать петли - это хорошо, но компилятор уже делает это и будет делать это лучше, чем вы, большую часть времени.

Чтобы подключить мою любимую функцию языка, ее лучше было бы использовать с использованием шаблонов: простая реализация (возможно, более умная) будет выглядеть так:

// I'm sure the compiler can figure out the inline part, but I'll add it anyways
template<unsigned int="" n=""> 
inline void ****************(******** v) {
 m_data[m_dataOffset + N] = v - v / 10 * 10 + 48;
 ****************<n-1>(v / 10);
}
// For situations just like this, there a trick to avoid having to define the base case separately.
inline void ****************<0>(******** v) {
 m_data[m_dataOffset] = v - v / 10 * 10 + 48;
}
template<unsigned int="" n="">
inline void *****************(******** v) {
 ****************<n-1>(v);
 m_dataOffset += N;
}
// We could generate the compile-time binary search with templates too, rather than by hand.
void *********(******** v, char d) {
 if (m_dataOffset + 11 > sizeof(m_data)) Flush();
 if (v < 100000) {
 if (v < 1000) {
 if (v < 10) {
 *****************<1>(v);
 } else if (v < 100) {
 *****************<2>(v);
 } else {
 *****************<3>(v);
 }
 } else {
 if (v < 10000) {
 *****************<4>(v);
 } else {
 *****************<5>(v);
 }
 }
 } else {
 if (v < 100000000) {
 if (v < 1000000) {
 *****************<6>(v);
 } else if (v < 10000000) {
 *****************<7>(v);
 } else {
 *****************<8>(v);
 }
 } else {
 if (v < 1000000000) {
 *****************<9>(v);
 } else {
 *****************<10>(v);
 }
 }
 }
 m_data[m_dataOffset++] = d;
}
</n-1></unsigned></n-1></unsigned>

Делает ли такие вещи, как эта хорошая практика кодирования в целом? Да, но только если удовлетворяются все следующие критерии:

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

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

  • Когда вы отлаживаете, возможность вернуться к простой версии поможет сузить места, где могут быть проблемы.
  • Когда вы пытаетесь запустить на другом компьютере (или даже на том же компьютере в разных условиях), вы можете обнаружить, что сложная версия не быстрее, чем простая версия.


попробуйте это для более быстрого ввода-вывода

ios_base:: sync_with_stdio (ложь); cin.tie(NULL);

Он устанавливает, синхронизируются ли стандартные потоки С++ со стандартными потоками C после каждой операции ввода/вывода. По умолчанию объекты iostream и потоки cstdio синхронизируются.

licensed under cc by-sa 3.0 with attribution.