China DOS Union

Actually, I didn't test it. Analyzing from the algorithm, I know that without testing, the time is the same. It's just that the variables used are different. The triple loop might be slightly more time-consuming theoretically.

Originally posted by plp626 at 2008-4-12 23:20:
Actually, I didn't test it. From an algorithm analysis, I knew that without testing, the time would be the same. It's just that different variables are used. The three - layer loop might theoretically take a little more time.

You really analyzed it from the algorithm? The time complexities are not the same!
It's still called that the time is the same without testing...


I can guarantee that the tested time will definitely be different!

Just different variables are used...? Is it really like this?
The three - layer loop. In traditional programming, there is 1 x1 (constant), 1 x10, and one x100 (that example seems to be that abc can be combined directly. This is the support of set in P. ) Adding them up gets that three - digit number. (Arithmetic operations are faster than character operations.)
Then compare with the sum of cubes of each...

This is the core operation. Determine the time complexity according to the number of loop times. One is O(10^(n+1)-10^(n+1)/9)=O(10^n*8/9), and the other is O(9^n)

The larger the number, the higher the efficiency of the second algorithm!

If judging three - digit numbers:
The first kind: O(999-111+1)=O(889)
The second kind: O(9*9*9)=O(729)
If judging ten - digit numbers:
The first kind: O(8888888889)
The second kind: O(3486784401)

If judging twenty - digit numbers:
The first kind: O(88888888888888888889)
The second kind: O(12157665459056928801)

When it's twenty - digit, the number of loops is nearly 8 times!
It's not necessary to argue about three - digit numbers...
If you are fast enough yourself, you can play with more digits by yourself...

Which algorithm of set is faster, I really don't know.
Is there any difference in efficiency between the following two codes? I thought code one should be faster?
:

@echo off

:: Code one

for /l %%a in (10000 1 99999) do echo %%a

:: Code two

for /l %%a in (1 1 9) do (

  for /l %%b in (0 1 9) do (

    for /l %%c in (0 1 9) do (

      for /l %%d in (0 1 9) do (

        for /l %%e in (0 1 9) do (

           echo %%a%%b%%c%%d%%d

)))))

pause

Everyone is bored. Now I feel more bored than everyone:
Paste the original one again. After carefully reading, the number of loop times of the two codes are respectively:
For the 15th floor: 999 - 100 + 1 = 900 times
For the 19th floor: 9 * 9 * 10 = 900 times
Then analyze the statements used in the loop body:

For the 15th floor: one set direct assignment + 3 set/a assignments + 3 variable interceptions + 1 set/a arithmetic operation (sum of cubes) + one judgment output
For the 19th floor: one set direct assignment + 3 set/a assignments + 1 set direct assignment (merging) + 1 set/a arithmetic operation (sum of cubes) + one judgment output

Everyone is really boring, simply dreadful,
Well, now
I've made a decision,
Ready to be more boring than everyone:

Paste the original again, read carefully, the number of loop iterations for the two codes are respectively:
For the 15th floor: 999-100+1=900 times (1 loop)
For the 19th floor: 9*10*10= 900 times (3 loops)
Then analyze the statements in the loop body:

For the 15th floor: one set direct assignment (set str=%%i) + 3 set/a assignments + 3 variable extractions + 1 set/a arithmetic operation (cube sum) + one judgment output (if !var! equ !str! echo !str!)
For the 19th floor: one set direct assignment (set num1=!a!!b!!c!) + 3 set/a assignments + (merge) + 1 set/a arithmetic operation (cube sum) + one judgment output (if !num1! equ !num2! echo !num1!)
For the 15th floor:

@echo off
setlocal enabledelayedexpansion
for /l %%i in (100,1,999) do (
set str=%%i
set/a a=!str:~,1!, b=!str:~1,1!, c=!str:~2,1!
set /a var=!a!*!a!*!a!+!b!*!b!*!b!+!c!*!c!*!c!
if !var! equ !str! echo !str!
)
pause

For the 19th floor:

@echo off
setlocal enabledelayedexpansion
for /l %%i in (1,1,9) do for /l %%j in (0,1,9) do for /l %%k in (0,1,9) do (
set/a a=%%i,b=%%j,c=%%k
set num1=!a!!b!!c!
set /a num2=!a!*!a!*!a!+!b!*!b!*!b!+!c!*!c!*!c!
if !num1! equ !num2! echo !num1!
)
pause

The following is my analysis, (I'm not from a computer background, batch processing is just a hobby, don't laugh at me if I say something wrong)

With the same number of loop iterations, different numbers of loop levels, the time taken is different. More loop levels mean more instructions, and more time is spent. So it seems that the loop on the 15th floor takes less time.

The problem is with variable extraction, which takes time. And that so-called "merge" of !a!!b!!c! is just putting three variables together, while
a=!str:~,1!, b=!str:~1,1!, c=!str:~2,1!
This corresponds to some instructions telling the interpreter which parts of str are extracted and assigned to variables a, b, c, which takes some time.
So it seems that the statements in the loop body on the 15th floor also take a little more time,

One short and one long, can they cancel out?

I haven't tried it,

Floor 34, I clicked the wrong one for the first time. I don't know why, but now I can't delete it. It affects browsing. Really annoying.

Anyway, everyone's attitude towards researching problems really makes me admire! At the same time, I think that when the running time value of the batch processing itself is within 0.01 seconds (the system can't detect the error value at all), there is really no need to argue about efficiency issues. Instead, we should focus more on researching and discussing the methods of handling problems, such as researching code structure, operation logic, ideas, and starting points. Personally, I think this is where we need to delve into most. I wonder what everyone thinks.

Hey~ Getting old. I was wrong... Got confused with another program I wrote.

That program doesn't have 0... So each loop is from 1 to 9
Counted as 9 times...

For the narcissistic number, the first digit is 9 and the others are 10...
But handling characters is definitely slower than numbers, and merging is faster.

Also confirmed:
Narcissistic numbers only refer to 3-digit numbers... So there won't be too large numbers... So the speed difference can be ignored.

So sorry for talking so much and misleading.

PS: When you use C, you'll know that handling each digit as characters is cumbersome, and handling as numbers is also cumbersome needing to take remainders... But multiplying by 10 or *100 is easy...