Какой самый быстрый класс C ++ или библиотека C для преобразования широты и долготы из десятичных градусов в строку и обратно

Question

Я ищу лучший код C или C ++ для кодирования и декодирования десятичных значений широты и долготы от / до double / char. Я бы предпочел преобразовать код из double в char [] и наоборот вместо строк с ++.

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

Чтобы уточнить: мне нужно преобразовать из строки градусы / минуты / секунды в удвоение и обратно в строку. У меня есть 300 миллионов записей, поэтому скорость - большая проблема.

См .: http://en.wikipedia.org/wiki/Geographic_coordinate_conversion

Answer 1

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

Аманда сообщает, что она работает где-то в 15x быстрее, чем код, который они использовали.
Учитывая, что это более 300 миллионов записей, это должно быть довольно существенной экономией времени.

Я нашел проблему очень интересной.

Вот код:

/* WARNING:  These values are very important, as used under the "default" case. */
#define INT_PART 3
#define DEC_PART 2

double Str2LatLong(char* coord)
//double LLStr::Str2LL(char* coord)
{
    int sign = +1;
    double val;

    int i = 0;  /* an index into coord, the text-input string, indicating the character currently being parsed */

    int p[9] = {0,0,1,  /* degrees */
                0,0,1,  /* minutes */
                0,0,1   /* seconds */
               };
    int* ptr = p;   /* p starts at Degrees. 
                       It will advance to the Decimal part when a decimal-point is encountered,
                       and advance to minutes & seconds when a separator is encountered */
    int  flag = INT_PART; /* Flips back and forth from INT_PART and DEC_PART */

    while(1)
    {
        switch (coord[i])
        {
            /* Any digit contributes to either degrees,minutes, or seconds */
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                *ptr = 10* (*ptr) + (coord[i] - '0');
                if (flag == DEC_PART)  /* it'd be nice if I could find a clever way to avoid this test */
                {
                    ptr[1] *= 10;
                }
                break;

            case '.':     /* A decimal point implies ptr is on an integer-part; advance to decimal part */
                flag = DEC_PART; /* after encountering a decimal point, we are now processing the Decimal Part */
                ptr++;  /* ptr[0] is now the Decimal piece; ptr[1] is the Denominator piece (powers of 10) */
                break;

            /* A Null terminator triggers return (no break necessary) */
            case '\0':
                val = p[0]*3600 + p[3]*60 + p[6];             /* All Integer math */
                if (p[1]) val += ((double)p[1]/p[2]) * 3600;  /* Floating-point operations only if needed */
                if (p[4]) val += ((double)p[4]/p[5]) *   60;  /* (ditto) */
                if (p[7]) val += ((double)p[7]/p[8]);         /* (ditto) */
                return sign * val / 3600.0;                 /* Only one floating-point division! */

            case 'W':
            case 'S':
                sign = -1;
                break;

            /* Any other symbol is a separator, and moves ptr from degrees to minutes, or minutes to seconds */
            default:
                /* Note, by setting DEC_PART=2 and INT_PART=3, I avoid an if-test. (testing and branching is slow) */
                ptr += flag;
                flag = INT_PART; /* reset to Integer part, we're now starting a new "piece" (degrees, min, or sec). */
        }
        i++;
    }

    return -1.0;  /* Should never reach here! */
}

Answer 2

Вот код, который я разработал:

double Str2LatLong(char* coord)
{
    // char* testInput = "47,26'14\"";

    int i = 0;
    int parts[3] = {0};  // parts[0] is degrees, parts[1] is minutes, parts[2] is seconds
    int* pCurr = parts;

    do
    {
        if (coord[i] == '\0')
        {
            break;
        }
        if (!isdigit(coord[i]))
        {
            *pCurr++; // skip from parts[0] ==> [1], or [1] ==> [2]
            continue;
        }
        *pCurr = 10* (*pCurr) + coord[i] - '0';
        ++i;
    } while (1);

    return parts[0] + ((double)parts[1])/60.0 + ((double)parts[2])/3600.0;
}

Поскольку он написан для скорости, проверка ввода НЕ производится.
Вы должны предоставить правильный ввод, иначе он будет плохо работать.

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

Только в самой последней строке он преобразуется в удвоенную с некоторыми оченьпростые операции с плавающей точкой.

Я подозреваю, что вы захотите изменить его так, чтобы он обрабатывал положительные / отрицательные значения, а также индикаторы Север / Юг, Восток / Запад и десятичные знаки после секунд.Но я думаю, что этот код является хорошей основой для очень быстрой процедуры преобразования.

Я надеюсь, что это очень быстро протестируется.Пожалуйста, дайте мне знать, как это происходит.

Answer 3

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

Answer 4

Вот еще один вариант.

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

Вы должнытакже можно улучшить этот с

case 'N':
case 'S':
case 'E':
case 'W': 

по мере необходимости.

double Str2LatLong(char* coord)
{
    // char* testInput = "47,26'14\"";

    int i = 0;
    int parts[3] = {0};
    int* pCurr = parts;

    while(1)
    {
        switch (coord[i])
        {
            /* Any digit contributes to either degrees,minutes, or seconds (as *pCurr) */
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                *pCurr = 10* (*pCurr) + coord[i] - '0';
                break;

            /* A Null terminator triggers return (no break necessary) */
            case '\0':
                return parts[0] + ((double)parts[1])/60.0 + ((double)parts[2])/3600.0;

            /* Any other symbol moves pCurr from degrees to minutes, or minutes to seconds */
            default:
                *pCurr++;
        }
        i++;
    }

    return -1.0;  /* Should never reach this point! */
}

Answer 5

C ++ строки и потоки - очень хорошая идея, но если вы абсолютно не можете их использовать, следующий код может быть полезен. Первая функция записывает два типа double в существующую строку C. Вторая функция считывает два двойных числа из существующей C строки и возвращает их по указателю:

void CoordinatesToString(double lat, double long, char *buffer, size_t len) {
    assert(buffer != NULL);
    assert(len > 0);

    snprintf(buffer, len, "%f, %f", lat, long);
    buffer[len - 1] = 0; /* ensure null terminated */
}

int StringToCoordinates(const char *string, double *outLatitude, double *outLongitude) {
    assert(string != NULL);
    assert(outLatitude != NULL);
    assert(outLongitude != NULL);

    return (2 == sscanf(string, "%f, %f", outLatitude, outLongitude));
}

Использование:

char buffer[128];
CoordinatesToString(90.0, -33.0, buffer, 128);

double lat, lng;
if (StringToCoordinates(buffer, &lat, &lng)) {
    printf("lat: %f long %f\n", lat, lng);
}

НО. C ++ строки предназначены для такого рода использования. Они не страдают от потенциальных проблем переполнения, свойственных массивам char, и вам не нужно вручную управлять их памятью - они изменяют размер, чтобы соответствовать их содержимому по мере необходимости. Есть ли причина , почему вы хотите избежать std::string, когда говорите, что с C ++ все в порядке?