Mensajes

Sí sí, es que quería mantener una atmósfera de misterio...

Las pruebas las hice con:

Código (cpp) [Seleccionar] Expandir

size_t n_pares(const std::vector<int>& v, int k)
{
    auto n{ 0 };
    auto it{ v.begin() };

    for (auto i = v.begin(), j = v.end();
        i < j;
        ++i)  // avanza la cola
    {
        while (it != j && *it < *i + k) {  // avanza la cabeza
            ++it;
        };

        if (it == j) { // no tanto que se caiga
            break;
        }

        else if (*it == *i + k) {  // se ha formado una pareja
            ++n;
        }
    }

    return n;
}

Y ejecutando la misma prueba para cada una de las tres funciones, en Visual Studio, ha resultado:

Visual Studio:
-------------

Elementos al azar (uniform distribution) desde 1 hasta 2147483647
k == 25


Vector size == 99998

n_pares():
hallados == 7
demora: 0.0002385 seg

k_paired():
hallados == 7
demora: 0.0003567 seg (49.5597 %)

k_zoz():
hallados == 7
demora: 0.0005064 seg (112.327 %)


Vector size == 999767

n_pares():
hallados == 462
demora: 0.002672 seg

k_paired():
hallados == 462
demora: 0.0038684 seg (44.7754 %)

k_zoz():
hallados == 462
demora: 0.005371 seg (101.01 %)


Vector size == 9974491

n_pares():
hallados == 46567
demora: 0.0346364 seg

k_paired():
hallados == 46567
demora: 0.0532758 seg (53.8145 %)

k_zoz():
hallados == 46567
demora: 0.0667464 seg (92.7059 %)


Vector size == 97464998

n_pares():
hallados == 4419710
demora: 0.796983 seg

k_paired():
hallados == 4419710
demora: 0.922205 seg (15.712 %)

k_zoz():
hallados == 4419710
demora: 1.12035 seg (40.5734 %)


Vector size == 783463366

n_pares():
hallados == 285828837
demora: 6.97443 seg

k_paired():
hallados == 285828837
demora: 8.55857 seg (22.7136 %)

k_zoz():
hallados == 285828837
demora: 9.50019 seg (36.2146 %)

Curioso, al menos a mí me lo parece.

Pero lo mismo con Mingw (g++ -O3 -Wall -pedantic)
resulta:

Elementos al azar (uniform distribution) desde 1 hasta 2147483647
k == 25


Vector size == 99997

n_pares():
hallados == 5
demora: 0.000945 seg

k_paired():
hallados == 5
demora: 0 seg (-100 %)

k_zoz():
hallados == 5
demora: 0 seg (-100 %)


Vector size == 999744

n_pares():
hallados == 456
demora: 0.002965 seg

k_paired():
hallados == 456
demora: 0.003038 seg (2.46206 %)

k_zoz():
hallados == 456
demora: 0.003999 seg (34.8735 %)


Vector size == 9974357

n_pares():
hallados == 46171
demora: 0.046053 seg

k_paired():
hallados == 46171
demora: 0.033003 seg (-28.3369 %)

k_zoz():
hallados == 46171
demora: 0.048001 seg (4.22991 %)


Vector size == 97462426

n_pares():
hallados == 4422382
demora: 0.875945 seg

k_paired():
hallados == 4422382
demora: 0.785002 seg (-10.3823 %)

k_zoz():
hallados == 4422382
demora: 0.966 seg (10.2809 %)


Vector size == 783434184

n_pares():
hallados == 285793753
demora: 7.66395 seg

k_paired():
hallados == 285793753
demora: 7.158 seg (-6.60165 %)

k_zoz():
hallados == 285793753
demora: 8.702 seg (13.5446 %)

Jé, nuevo desafío... ¿quién me lo explica?

Por si hubiera alguien más interesado:

Tengo una variante prácticamente un 20% más rápida; ¿alguien más quiere probar suertes y poner aquí sus resultados?

[Visual Studio 2019 v.16.2.5] (((NOTA de Interés... al menos para mí... Con Mingw g++ 8.2.0 no encuentro ninguna diferencia)))

Elementos al azar (uniform distribution) desde 1 hasta 2147483647
k == 25


Vector size == 99999

k_paired():
hallados == 6
demora: 0.0002796 seg

n_pares():
hallados == 6
demora: 0.0002281 seg (-18.4192 %)


Vector size == 999748

k_paired():
hallados == 484
demora: 0.0031284 seg

n_pares():
hallados == 484
demora: 0.0024078 seg (-23.0341 %)


Vector size == 9974323

k_paired():
hallados == 46206
demora: 0.0451042 seg

n_pares():
hallados == 46206
demora: 0.0338307 seg (-24.9943 %)


Vector size == 97464323

k_paired():
hallados == 4423642
demora: 0.889701 seg

n_pares():
hallados == 4423642
demora: 0.778881 seg (-12.4559 %)


Vector size == 783444620

k_paired():
hallados == 285821970
demora: 8.40441 seg

n_pares():
hallados == 285821970
demora: 6.8764 seg (-18.181 %)

Está bien,

pero este algoritmo "k_paired" se comporta realmente en forma lineal. Lo modifiqué mínimamente para hacer una comparación:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <numeric>
#include <chrono>

int k_paired(const std::vector<int>& V, const int k)
{
    size_t n, m, r;

    for (n = m = r = 0; n < V.size();)
    {
        if (V[n] - V[m] <= k) {
            r += (V[n++] - V[m] == k);
        }

        else {
            m++;
        }
    }

    return r;
}

int main()
{
    std::vector<int> v4(1000, 0);

    for (int i = 1; i < 6; ++i) {
        v4.resize(v4.size() * 10);
        std::iota(v4.begin(), v4.end(), 0);

        std::cout << "v4.size() == " << v4.size() << '\n';

        // comienza a contar... desde acá
        auto start = std::chrono::high_resolution_clock::now();
        std::cout << k_paired(v4, 37) << '\n';
        // hasta acá.
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed = finish - start;
        std::cout << "demora: " << elapsed.count() << " seg\n\n";
    }
}

Con estos resultados:

k_paired               
------------           

v4.size() == 10000      
9975                   
demora: 0.0001789 seg   
                       
v4.size() == 100000     
99975                   
demora: 0.0004935 seg   
                       
v4.size() == 1000000   
999975                 
demora: 0.0037331 seg   
                       
v4.size() == 10000000   
9999975                 
demora: 0.03295 seg     
                       
v4.size() == 100000000 
99999975               
demora: 0.32598 seg     
                       

Se lo ve muy lineal, ciertamente; y sobre todo, 10 veces más rápido que usando lower_bound; nada mal.

Pero la versión con lower_bound (que llamé "n_pares") no es O(Nlog(N)), es en realidad prácticamente equivalente a k_paired, también avanza como un gusano, y creía que debía comportarse de la misma manera, con un desenvolvimiento lineal, aunque resultó 10 veces más lento. Un oprobio. Si te fijas en esta línea:

Código [Seleccionar] Expandir

it = std::lower_bound(it, j, s); it queda posicionado en la posición buscada o en una más allá del límite s, esperando en el mejor lugar para la próxima iteración. Y lower_bound es un binary search, logarítmico, que es mejor que avanzar secuencialmente, o mejor dicho, creí que debería serlo.

Casualmente justo ayer Andrei Alexandrescu dio una charla sobre estas cuestiones en la CppCon, y comentaba que después de fracasar con todas las soluciones inteligentes comenzó a probas las estúpidas; y, sorpresa...

[youtube=640,360]https://www.youtube.com/watch?v=FJJTYQYB1JQ[/youtube]

Si esto no se pone demasiado pesado, comento que:

Yo también probé con una solución (aparentemente) muy inferior a la versión con lower_bound, donde lo reemplazo por un estúpido find, haciendo ahora sí una solución (prácticamente) O(N2), pero no, curiosamente:

Código (cpp) [Seleccionar] Expandir

size_t n_pares(const std::vector<int>& v, int k)
{
    assert(std::is_sorted(v.begin(), v.end()) && "v debe estar ordenado.");
    assert(v.size() && "v no puede venir vacio.");

    auto n{ 0u };
    auto it = v.begin();

    for (auto i = v.begin(), j = v.end(); i != j; ++i)
    {
        it = std::find(it, j, *i + k);

        if (it != j) {
            ++n;
            ++it;
        }
        else {
            it = i + 1;
        }
    }

    return n;
}

Ahora los resultados son hasta ligeramente mejores que los de los de k_paired. Joder.

Código [Seleccionar] Expandir


k_paired                                    n_pares
------------                                ------------

v4.size() == 10000                          v4.size() == 10000
9975                                        9975
demora: 0.0001789 seg                       demora: 0.0001686 seg

v4.size() == 100000                         v4.size() == 100000
99975                                       99975
demora: 0.0004935 seg                       demora: 0.0004539 seg

v4.size() == 1000000                        v4.size() == 1000000
999975                                      999975
demora: 0.0037331 seg                       demora: 0.0026152 seg

v4.size() == 10000000                       v4.size() == 10000000
9999975                                     9999975
demora: 0.03295 seg                         demora: 0.0266995 seg

v4.size() == 100000000                      v4.size() == 100000000
99999975                                    99999975
demora: 0.32598 seg                         demora: 0.26099 seg


UN mundo muy ingrato.

Para los que se las arreglan con el inglés vale la pena también el histórico:
"CPU cache and why you care" de Scott Meyers: https://youtu.be/3G-LO9T3D1M

Edito...
Acomodo un poco que puede hacerse un pelín más claro y algo más rápido

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <numeric>
#include <chrono>

size_t n_pares(const std::vector<int>& v, int k)
{
    assert(std::is_sorted(v.begin(), v.end()) && "v debe estar ordenado.");
    assert(v.size() && "v no puede venir vacio.");

    auto n{ 0 };
    auto it = v.begin();

    for (auto i = v.begin(), j = v.end();
        i != j && it != j;
        ++i)
    {
        auto s = *i + k;
        it = std::lower_bound(it, j, s);

        if (it != j && *it == s) {
            ++n;
            ++it;
        }
    }

    return n;
}

int main()
{
    std::vector v1{ 1, 4, 5, 6, 8 };
    std::vector v2{ 1, 4, 5, 6 };
    std::vector v3{ 1, 2, 3 };

    std::cout << n_pares(v1, 3) << '\n';
    std::cout << n_pares(v2, 2) << '\n';
    std::cout << n_pares(v3, 0) << '\n';

    std::vector<int> v4(1000, 0);

    for (int i = 1; i < 6; ++i) {
        v4.resize(v4.size() * 10);
        std::iota(v4.begin(), v4.end(), 0);

        std::cout << "v4.size() == " << v4.size() << '\n';

        // comienza a contar... desde acá
        auto start = std::chrono::high_resolution_clock::now();
        std::cout << n_pares(v4, 25) << '\n';
        // hasta acá.
        auto finish = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed = finish - start;
        std::cout << "demora: " << elapsed.count() << " seg\n\n";
    }

    std::cout << "No es perfectamente lineal, pero solo se abre un poco a partir de los 100 millones.\n";
}

Sabes que mas de perdió de aquella época? parece ser el respeto, tu sarcasmo sobra.

Primero, estoy aprendiendo a programar y así es como me lo están enseñando. Segundo, si eres un amargado de la vida mejor postea en otro sitio, gracias ^.^

Mis disculpas, pero la cosa no era contigo que eres la víctima. Sucede que por alguna razón hay una manía de enseñar C++ como si se estuviera en los 70s, con construcciones y rutinas propias de los 50. Y no sé muy bien por qué, pero me disgusta de sobremanera. Yo también he tenido que pasar por el mismo tratamiento de quienes enseñar vicios y usan el poder de una cátedra para que todo el mundo esté obligado a reproducirlos. Me parece francamente despreciable, y no conseguí decirlo bien.

Va una aclaración por si sirviera:

La construcción

Código [Seleccionar] Expandir

while (!Archivo.eof()){
es por lo menos incompleta, ya la suspensión de la lectura con getline puede deberse a más de una causa.

std::ifstream tiene un operator bool, que equivale a !fail(), que es lo que permite la lectura en ciclos.
Documentación: https://en.cppreference.com/w/cpp/io/basic_ios/operator_bool

La forma canónica sería:

Código (cpp) [Seleccionar] Expandir

    while (std::getline(Archivo, Frase)) {
        std::cout << Frase << std::endl;
    }

    // Si interesa saber que ha resultado:
    // (puedes consultar la documentaciOn:
    // https://en.cppreference.com/w/cpp/io/ios_base/iostate

    if (Archivo.good())
        std::cout << "Sin error.\n";
    else if (Archivo.eof())
        std::cout << "End of file.\n";
    else if (Archivo.fail())
        std::cout << "Error de lectura.\n";
    else if (Archivo.bad())
        std::cout << "Error irrecuperable.\n";

Código [Seleccionar] Expandir

while (!Archivo.eof()){
std::getline(Archivo,Frase);
std::cout << Frase << std::endl;
}

ese es un error muy común, un trozo de código fósil, que vaya a saber por qué se repite meticulosamente en los primeros palotes. ¿Mucho copiar y pegar el código de malos programadores del siglo XX?  (Ah, por las dudas, XX se lee "veinte")

Bueno, si te fijas un poco en lo que hace ese fragmento de código, Archivo no tiene activa la señal de eof hasta que no se pretenda leer más allá de la última linea, o ¿de qué otra manera sabría Archivo que se ha alcanzado la última?

A modo de curiosidad histórica, hace muchos, muchos años, creo que la última vez que se vio fue alrededor de 1960, los archivos se guardaban en cintas magnéticas, y cuando un archivo tenía una parte en una cinta y otra parte en otra, era necesario poner una "marca de fin de archivo" (de ahí el nombre eof - end of file). Entonces, un archivo tenía al final esa marca, normalmente 0xFFFF, que si fuera un int se leería como -1. Pero eso era así en la época en tus abuelos se conocieron, desde entonces las cosas han cambiado un poco, y algo que cambió son los filesystems, de modo que los archivos ya no llevan una "marca de fin de archivo", nunca más, desde hace muuuuucho tiempo.

[Ventajas?]

se desea redondear un entero positivo N a la centena mas proxima y visualizar la salida.
Para ello la entrada de datos debe de sr los cuatro digitos A,B,C,D del entero N. Por ejemplo, si A es 2, B es 3, C es 6 y D es2, entonces N será 2362 y el resultado redondeado será 2400. SiN es 2342, el resultado seeá 2300 , y si  N=2962, entonces el numero será 3000

En C++ moderno es inmediato, por ejemplo:

Código (cpp) [Seleccionar] Expandir

#include <cmath>
#include <iostream>

long redondear_a_la_centena(int n) {
    return std::lround(n / 100.0) * 100;
}

int main()
{
    std::cout << "2362 redondedo a la centena: " << redondear_a_la_centena(2362) << '\n';
    std::cout << "2342 redondedo a la centena: " << redondear_a_la_centena(2342) << '\n';
    std::cout << "2962 redondedo a la centena: " << redondear_a_la_centena(2962) << '\n';
}


Ventajas?
Ver la documentación, en especial "Error handling"
https://en.cppreference.com/w/cpp/numeric/math/round

Parece que te han tomado el pelo. Ya no se usan pesetas, ahora son euros.

[extern]

ok, entiendo, pero yo tenía entendido que cuando tu definías algo, estas usando el constructor... o es que extern es la excepción?

Exactamente, así es; extern es para indicar que se trata de una declaración, no una definición, por eso es que la definición debe ir en algún otro lado.

De todos modos hoy (a partir del C++17) es preferible la declaración inline https://en.cppreference.com/w/cpp/language/inline

Sin embargo, acabo de darme cuenta que incializar y definir no son la misma cosa...

... Más o menos... o, mejor, casi nunca...
Declarar, definir, inicializar, son palabras que tienen significados muy específicos, y con unos cuantos casos particulares, que algunas veces no ayudan para nada a la intuición.

En algunos casos la declaración y la definición son la misma cosa;
En casi todos los casos una definición implica la inicialización.

En matemática elemental tienes palabras como minuendo, sustraendo, resta, diferencia, que no pueden confundirse; o, también, dividendo, divisor, cociente, división. 0, ¿qué tal porciento, porcentaje, tasa, razón?  Cada una significa algo específico pero que en el habla común usamos sin mucho cuidado. Bueno, en C++ es mucho peor.

[extern]

Para objetos de alguna clase es lo mismo que para tipos nativos, puedes usar las dos formas, declarar el objeto como extern o como inline (mejor).

Por ejemplo, usando extern podría ser algo así:
Archivo1.h

Código [Seleccionar] Expandir

#pragma once
#include <string>

extern struct X {
   X(std::string str) : str(str) {}
   int num = 10;
   std::string str;
} x;

Y en algún cpp

Código [Seleccionar] Expandir

X x{"hola"};

Usando inline no necesitas que la definición esté en un cpp

Código [Seleccionar] Expandir

#pragma once
#include <string>

inline struct X {
   X(std::string str) : str(str) {}
   int num = 10;
   std::string str;
} x{"hola"};

Estos son un par de ejemplos de cómo podía hacerse antes y ahora con el estándar C++17, pero hay otras cosas a considerar, probablemente necesites un constructor por defecto, y asignarle valores a tu objeto cuando el programa los conozca, o crear el objeto en la memoria libre (usando un smart pointer, por supuesto), o ... Bueno, ya verás.

[EDITO] Ah, me olvidaba

O es que al escribir extern Sesion s en realidad no estoy ejecutando el constructor con su inicialización?

No, no estás ejecutando el constructor, porque extern Sesion es una declaración no una definición.