Question

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

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

#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
class FastInput {
public:
    FastInput() {
        m_dataOffset = 0;
        m_dataSize = 0;
        m_v = 0x80000000;
    }
    uint32_t 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:
    uint8_t m_buffer[32768];
    uint32_t m_data[16384];
    size_t m_dataOffset, m_dataSize;
    uint32_t 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 PrintUint(uint32_t 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:
    uint8_t m_data[32768];
    size_t m_dataOffset;
};

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

SigTerm · Answer 1 · 17 марта 2012

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

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

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

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

Фрагмент кода, о котором идет речь, использует несколько плохих методов кодирования:

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

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

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

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

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

Aakash Malhotra · Answer 2 · 24 августа 2015

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

ios_base :: sync_with_stdio (false);cin.tie (NULL);

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

Hurkyl · Answer 3 · 17 марта 2012

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

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

// I'm sure the compiler can figure out the inline part, but I'll add it anyways
template<unsigned int N> 
inline void print_uint_inner(uint32_t v) {
    m_data[m_dataOffset + N] = v - v / 10 * 10 + 48;
    print_uint_inner<N-1>(v / 10);
}

// For situations just like this, there's a trick to avoid having to define the base case separately.
inline void print_uint_inner<0>(uint32_t v) {
    m_data[m_dataOffset] = v - v / 10 * 10 + 48;
}

template<unsigned int N>
inline void print_uint_helper(uint32_t v) {
    print_uint_inner<N-1>(v);
    m_dataOffset += N;
}

// We could generate the compile-time binary search with templates too, rather than by hand.
void PrintUint(uint32_t v, char d) {
    if (m_dataOffset + 11 > sizeof(m_data)) Flush();
    if (v < 100000) {
        if (v < 1000) {
            if (v < 10) {
                print_uint_helper<1>(v);
            } else if (v < 100) {
                print_uint_helper<2>(v);
            } else {
                print_uint_helper<3>(v);
            }
        } else {
            if (v < 10000) {
                print_uint_helper<4>(v);
            } else {
                print_uint_helper<5>(v);
            }
        }
    } else {
        if (v < 100000000) {
            if (v < 1000000) {
                print_uint_helper<6>(v);
            } else if (v < 10000000) {
                print_uint_helper<7>(v);
            } else {
                print_uint_helper<8>(v);
            }
        } else {
            if (v < 1000000000) {
                print_uint_helper<9>(v);
            } else {
                print_uint_helper<10>(v);
            }
        }
    }
    m_data[m_dataOffset++] = d;
}

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

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

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

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

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

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 3 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

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

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 3 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы