C++

Forum

 
How to make this code run more faster

Pages: 123
ne555 (10692)
For a to be a palindrome is either in the form b'b or b'xb where b' is reverse(b), and x is a digit
So, to count the number of palindromes that have six digits, you simply count the numbers that have three digits.


> Although the range is 1 million,
the range is not 1 million.
``For a given positive integer K of not more than 1000000 digits''
Last edited on
Catfish666 (666)
The times on SPOJ for this problem are suspicious. Consider the code below.
It still needs 0.09 seconds to run for the PALIN problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <stddef.h>
#include <stdio.h>

#define K_LIMIT     1000000 + 1

char k[K_LIMIT];

int main(void)
{
    size_t n=0;

    scanf("%zu", &n);

    for (; n != 0; --n)
    {
        scanf("%s", k);
        printf("%s\n", k);
    }
}
sanddy1911 (45)
Check the soluction provided here http://algorithm3.wordpress.com/2012/03/28/5-the-next-palindrome-palin/
It will take ~.06 sec to excute on SPOJ but when i change gets to scanf it will increase to ~.12 sec.
Last edited on
sanddy1911 (45)
Although the range is 1 million, the number have to be palindromes so you'll have (I think):
1000 6 digit numbers
1000 5 digit numbers
100 4 digit numbers
100 3 digit numbers
10 2 digit numbers
10 1 digit numbers

That's 2220 numbers. It's less than 2^11. You can search that with a binary search in less that 3ms on modern kit, never mind the 30ms required.


I dont understang,
Can you Explain or provide Pseudocode
cire (8284)
I dont understang,
Can you Explain or provide Pseudocode


For 1 digit numbers it is fairly straight forward: The numbers 0 to 9 are palindromes which gives us 10.

For 2 digit numbers, it isn't quite so straight forward (unless you consider 00 to be a possibility, but I would assume it isn't, unless specifically allowed for.) We have:
11, 22, 33, 44, 55, 66, 77, 88, and 99. For a total of 9 palindromes.

For 3 digit numbers, the middle digit has no bearing on whether the number is a palindrome or not. But, for the first digit we have the possibility of (1-9). In order to make a palindrome, the third digit must mirror the first. So we have 9 * 10 = 90 possible palindromes that consist of 3 digits.

For 4 digit numbers, again the leftmost digit must be 1-9, and the second digit can be any number from 0-9. The rightmost digits must mirror the left digits. So we have 9*10 = 90 possible palindromes that consist of 4 digits.

For 5 digit numbers, the leftmost digit must be 1-9. The second digit can be any number from 0-9. The middle digit doesn't have any bearing on whether the number is a palindrome or not, giving us 9*10*10 = 900 palindromes that consist of 5 digits.

For 6 digit numbers, the leftmost digit must be 1-9. The second and third digits can be any number from 0-9. So we have 9*10*10 = 900 palindromes consisting of 6 digits.
sanddy1911 (45)
Seems to be a good idea going to implement :)
Catfish666 (666)
Seems to be a good idea going to implement :)

I'm not so sure about that. One million digits will have a lot of palindromes.

@ cire: isn't there some permutations formula we could use?

So for example for 6 digit palindromes we have: 10P6 - x, where x represents the total number of invalid solutions, which start and end with zero.

I don't know how exactly to calculate x.

Edit: wait, I think I got it wrong...
Last edited on
ne555 (10692)
> isn't there some permutations formula we could use?
http://www.cplusplus.com/forum/general/118472/2/#msg647151
kbw (9488)
@Catfish666
I'm not so sure about that. One million digits will have a lot of palindromes.
As @cire showed, there really arn't that many. And my wild estimate showed that there are less than 211. And using a binary search, that'll be around 11 comparisons on a 2K int array.

If had the time I'd do show the search time on a Raspberry PI. But you shouldn't expect the search time to take more than 3ms.
ne555 (10692)
.oi there are 10^500000 palindromes that have no more than one million digits.

a little less if you don't count the ones that start with 0, so let's say about 10^499999
Last edited on
Catfish666 (666)
kbw wrote:
But you shouldn't expect the search time to take more than 3ms.

I am very interested in someone posting a solution to demonstrate this binary search.

However, I have to wonder:
1) when will the palindrome list be generated (runtime or compile-time?)
2) how exactly to choose best partially matching palindrome
3) how to get down at 0.03 when merely input/output takes 0.09
http://www.cplusplus.com/forum/general/118472/2/#msg647202

@ ne555: I found this article:
http://www.mathsisfun.com/combinatorics/combinations-permutations.html

So for six digit palindromes we have:
103 - 102 = 1,000 - 100 = 900

Above the 102 represents palindromes like 012210 which we don't accept.
However I'm still a bit confused about odd length palindromes.
Lowest0ne (1536)
But you shouldn't expect the search time to take more than 3ms.


And what about the creation ( and destruction ) of the tree?

I uploaded a random number to work with:
https://gist.github.com/Lowest0ne/7786971
sanddy1911 (45)
Is anyone going to demonstrate the binary search. I'm very curious to see.
Catfish666 (666)
Is anyone going to demonstrate the binary search. I'm very curious to see.

I believe kbw had in mind using the bsearch() function on an ordered array of all possible palindromes:

http://www.cplusplus.com/reference/cstdlib/bsearch/

However, the difficulty of writing the program simply shifts... from writing the algorithm as we had so far... to building the array of palindromes. So the difficulty is still intact, but transmogrified.

And this is why I asked in the previous post: when do we build the array, and how to compare the palindromes so that we find the partial matches we want to find?
ne555 (10692)
> However I'm still a bit confused about odd length palindromes.
say `n' is the number of digits of the number
10^n is the number of numbers that have `n' digits or less.
If you chose the first digit to be 0, then you've got 10^(n-1) possibilities
So the number of numbers that have `n' digits is 10^n - 10^(n-1) = 9*10^(n-1)


About palindromes. Divide the number in two portion of equal length
That means ab if `n' is even and axb if `n' is odd, where `x' is just one digit.
`b' is completely determined by `a'. In fact b = reverse(a)
`x' is independent.

So to count the number of palindromes, count `a' and multiple by 10 if `x' exists (if n is odd)
a -> 10^{floor(n/2)} - 10^{floor(n/2)-1} = 9 * 10^{(floor(n/2)-1}
ax -> 9 * 10^{floor(n/2)}


For 1000000 digits, you'll have 9*10^499999. That would enter in a tree of ~1.661e6 levels. That's quite close to number of digits, so your algorithm is still linear.
Last edited on
sanddy1911 (45)
I dont know what you guys are really wana say. in the most post you argue about the binary search. I try to implement it but i stuck on the beginning so if someone really know how to implement binary search than post a running code or at least a working Pseudocode. and if no one can do this than dont argue for binary search because implementing a binary search is not so easy as you guys are saying.

I totally agree with the Catfish666 argument
the difficulty of writing the program simply shifts... from writing the algorithm as we had so far... to building the array of palindromes. So the difficulty is still intact, but transmogrified.
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
 
"Set construction"
[1..10^500000] do:[|K|
   s insert: (K append: (K reverse)).
   [0..9] do:[|L|
      s insert: (K append: L append: (K reverse)).
   ]
]

"Search"
s upper_bound: number
kbw (9488)
Applying a binary search to a sorted array (or a tree) is pretty straightforward. But you don't have to write it from scratch, unless your lecturer requires it.
http://en.cppreference.com/w/cpp/algorithm/binary_search

Populating the collection is straightforward enough, just do as @cire described. Insert 1 digit values, then 2 digit values, ... up to 6 digit values.
Last edited on
JLBorges (13770)
One million digits was too little to be timed with any degree of accuracy;
it's been timed for ten numbers of ten million digits each.

The algorithm is linear on the number of digits; the time reported would be about 100 times greater than the (amortised) time required for a number with one million digits. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <iterator>

std::vector<int>& next_palindrome( std::vector<int>& number )
{
    if( number.empty() || number.front() == 0 ) return number = {1} ;

    auto begin = number.begin() ;
    auto end = number.begin() + number.size() / 2 + number.size()%2 ;
    std::reverse_iterator<decltype(end)> rbegin(end) ;
    std::reverse_iterator<decltype(end)> rend(begin) ;

    if( std::all_of( begin, end, []( int v ) { return v==9 ; } ) )
    {
        for( int& v : number ) v = 0 ;
        number.push_back(1) ;
        number.front() = 1 ;
        return number ;
    }

    else if( std::equal( rbegin, rend, begin+number.size()/2 ) ||
              std::lexicographical_compare( rbegin, rend,
                                               begin+number.size()/2, number.end() ) )
    {
        auto iter = rbegin ;
        while( *iter == 9 ) { *iter = 0 ; ++iter ; }
        ++ *iter ;
    }

    std::copy( begin, end, number.rbegin() ) ;
    return number ;
}

int main()
{
    {
        std::vector<int> test[]
        {
          std::vector<int>(30,9), { 1, 2, 3, 4, 5, 6, 7, 8 },
          { 6, 2, 3, 7, 5, 6, 7, 8 }, { 6, 9, 9, 9, 9, 9, 9, 9 },
          { 1, 2, 3, 4, 5, 0, 7, 8, 9 }, { 6, 2, 3, 4, 5, 6, 7, 8, 9 },
          { 5, 9, 9, 9, 6, 7, 7, 8, 9 }, { 1, 2, 3, 4, 5, 4, 3, 2, 1 },
          { 1, 2, 3, 4, 5, 5, 4, 3, 2, 1 }, { 8, 9, 9, 9, 9, 9, 9, 9, 9, 9 },
          { 1, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8 }
        };

        for( auto& number : test )
        {
            for( int v : number ) std::cout << v ;
            std::cout << '\n' ;
            for( int v : next_palindrome(number) ) std::cout << v ;
            std::cout << "\n\n" ;

        }
    }

    static std::mt19937 twister( std::time(nullptr) ) ;
    static std::uniform_int_distribution<> digit(0,9) ;
    static std::uniform_int_distribution<> non_zero_digit(1,9) ;

    constexpr std::size_t NDIGITS = 1000 * 1000 * 10 ; // 10 million digits
    std::vector<int> big( 1, non_zero_digit(twister) ) ;
    double ticks = 0 ;

    for( int i = 0 ; i < 10 ; ++i )
    {
        big.resize(1) ;
        while( big.size() < NDIGITS ) big.emplace_back( digit(twister) ) ;

        auto begin = std::clock() ;
        int x = next_palindrome(big).back() ;
        auto end = std::clock() ;
        if( x < 25 ) ticks += (end-begin) ;
    }
    std::cout << ticks / CLOCKS_PER_SEC << " seconds\n" ;
}

http://coliru.stacked-crooked.com/a/8620d37027e65c71
JLBorges (13770)
Optimized version of the same algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <vector>
#include <iterator>
#include <algorithm>

template < typename ITERATOR, typename ITERATOR2 >
bool less_or_equal( ITERATOR begin, ITERATOR end, ITERATOR2 begin2 )
{
    for ( ; begin != end ; ++begin, ++begin2 )
    {
        if( *begin < *begin2 ) return true ;
        if( *begin > *begin2 ) return false ;
    }
    return true ;
}

std::vector<int>& next_palindrome( std::vector<int>& number )
{
    if( number.empty() || number.front() == 0 ) return number = {1} ;

    auto begin = number.begin() ;
    auto end = number.begin() + number.size() / 2 + number.size()%2 ;
    std::reverse_iterator<decltype(end)> rbegin(end) ;
    std::reverse_iterator<decltype(end)> rend(begin) ;

    if( less_or_equal( rbegin, rend, begin+number.size()/2 ) )
    {
        auto iter = rbegin ;
        while( *iter == 9 && iter != rend ) { *iter = 0 ; ++iter ; }
        if( iter != rend ) ++ *iter ;
        else
        {
            std::fill( begin+number.size()/2, number.end(), 0 ) ;
            number.push_back(1) ;
            number.front() = 1 ;
            return number ;
        }
    }

    std::copy( begin, end, number.rbegin() ) ;
    return number ;
}
Pages: 123