|
The statistics you should capture in your output is the number of comparisons and number of swaps performed for each case. In the domain of complex objects, the comparison is likely more expensive then swapping a reference/pointer.
Classic bubble sort "back in the day" consisted of two for loops.
I think this approach is O(N log N).
Each inner iteration "bubbles" the min or max to the end of the list, so there is no reason to double check the constantly, moving last "bucket" on each iteration. The inner loop needs to run fewer iterations for each outer iteration.
for (int max = 0; max < length-1; ++max)
for (int i = 0; i < max; ++i) {
}
Combine this with your logic to stop if the list is in order and the number of comparisons should go down by log N.
Careful of infinite loops with this type of structure!
If this was written for a generic and someone passed in a poorly implemented operator> such that it returns:
a > b ==> true
b > a ==> true
then this code would result in an infinite loop where it keeps swapping values.
|
|
|
|
|
It's still O(n^2). What you're describing is a reduction in the coefficient of one of the terms; something Big-O doesn't measure but Big-Theta does. A logarithmic term requires recursive splitting of the input data such as divide and conquer approaches.
Bubble sorts time is sum_{n to 1}(n) = (n(n - 1)/2) = 0.5n^2 - 0.5n = O(n^2).
EDIT: Fixed a math error.
modified 30-Jan-20 15:22pm.
|
|
|
|
|
I see your point with the x(x+1)/2.
Technically it might be (x-1)(x)/2 since it is one less, but the magnitude is still the same.
|
|
|
|
|
Let me suggest that this was a VERY VERY important lesson to understand.
It is the basis for comparing algorithms for appropriate speed (to the problem and data at hand).
I chastised someone implementing a quicksort for < 100 items... (it was about 30 items, and would not be much larger, ever).
It helped me to discover Hash Indexing. I Created one that was 70% waste (only 30% of the values ever matched, and had ZERO duplicates). But it was 2 bytes. Another programmer challenged it with a binary tree, because he did NOT understand the nature of the lookup speed.
Finally, other algorithms that show you the importance of this: Calculate the Determinant of a square matrix. Write the code. It will look like a bubble sort. A 6x6 took 1 minute on my old computer, how long did the 7x7 take? 7 Minutes, I believe, the 8x8 was like 56 minutes (30yrs ago).
Converting to an upper/lower triangular reduces the time so amazingly you laugh. I wrote this to test my homework answers in my theory of matrices class. Quickly reviewing the algorithm told the entire story. I stuck with that FOREVER.
One lesson learned well...
BTW, I LOVED the videos of the various sorts... It is a beautiful explanation of what is going on.
|
|
|
|
|
I like the analyses and have studied how to compute the Big-O and Theta. I have also implemented every sorting algorithm I have ever seen (years ago). My only issue has been, how much brains does it require to understand that a loop inside a loop (the bubble) is not efficient.
The rest is just proving that you are right. Of course, for school, you have to provide the reason you are right and that is actually part of the fun of learning. But in the real world, they tend to take it for granted that you can see the obvious without actually calculating the Big-O.
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
During the holiday downtime last week I finally took the time to install a Let's Encrypt cert on the company's self-hosted web server. Because I'm impatient and not willing to wait hours for a txt record to propagate, I used the simple challenge test for a single named server. (wildcards require the txt method for verification) The cert was created for the canonical server name meaning that requests with the www prepended failed.
No problem, just add a couple of new url rewrite rules, one to remove the www. and the other to redirect to force https. It worked like a charm...or so I thought.
A week goes by without any reported problems until a customer goes to renew their contract. (desktop app) That's when all hell broke loose.  The desktop app sends a request to a registration web app hosted on that server that takes the querystring params and sends back a response indicating if the account is in good standing. This has worked well for many, many years so I was surprised when it started misbehaving. The problem turned out to be the querystring params were doubling. 
This was happening as a result of the url rewrite even though I had included the option to not append the querystring.  This was a problem due to the way multiple querystring paramaters with the same name are handled...basically, resource.aspx?sID=2&sID=2 resolves to '2,2'. Try parsing that to an int! (also, another reason to use TryParse vs. Parse)
Now, while that webpage/app was throwing a 500, the client-side app that was calling it became aware that an error had occurred and re-requested the page. It was only supposed to retry a maximum of 10 times before quitting...however, a line of code that made the request was mistakenly left right before the quit condition....  ...so, no matter what the fail counter said, it was going to keep trying...at least until the short variable hit it's limit!
This resulted in an unresponsive app for the client that had to be killed manually as well as a royal mess in the server's WC3 log.
Since this webserver is also used by other customers, I had to resort to handling the double parameters in the registration web app until after hours when I could correct the url rewrite rule. (use {URL} instead of {REQUEST_URI} in the redirect) In all, I had around a dozen different apps to fix on the server plus fixing and redeploying the desktop app. 
I was a bit surprised to realize that IIS's auto-ban had not kicked in until I discovered that it was not enabled. I could've sworn I enabled that a while back ...maybe that was the old server. (at least 2 years ago)
"Go forth into the source" - Neal Morse
|
|
|
|
|
Fun or what.
Services, with people using them, and expecting better.
|
|
|
|
|
I'll admit I did not read all that. But a year ago I ran into a problem at a company I was working for. There was another company that provide I black box, literally. Basically, it ask for some information and our system was too slow to provide it. So, it ask again. The issue was that we provided the information after a couple of request's, but it kept asking over and over again. I wrote a simple application to figure out what was going on. It turned out that the query (question) was ask continuously over a long period of time and all the answer's where apparently ignored.
Do to a bad design (in my opinion), we had over a 128 threads (up/down over time) querying the database for the same information that we had already provided to the black-box. It is my one and only experience of having a piece of equipment perpetrating a DOS attack on a system; even if it was not intentional.
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
apparently my company that is merged with another company and then split. Somewhere along the line. They(not sure who they is) bought some old ASP code for doing some calculations. Top of every ASP Page
`if strCurrentUserID = blnAdm OR blnPL then`
where strCurrentUSerID is something like 'rnbergren' and blnAdm and blnPL is a true/false value.
REwriting the entire thing to be `if (blnAdm or blnPL) then`
gesh!
the really fun thing is this has been in production for years! I mean years!
To err is human to really mess up you need a computer
|
|
|
|
|
rnbergren wrote: this has been in production for years! I mean years!
Then don't fix what aint broken. 
Social Media - A platform that makes it easier for the crazies to find each other.
Everyone is born right handed. Only the strongest overcome it.
Fight for left-handed rights and hand equality.
|
|
|
|
|
Just because it works does not mean that it is not broken. It is amazing the number of things duck-tape will fix.
INTP
"Program testing can be used to show the presence of bugs, but never to show their absence." - Edsger Dijkstra
"I have never been lost, but I will admit to being confused for several weeks. " - Daniel Boone
|
|
|
|
|
That strange feeling when you don't understand why some code is working 
Been there.
"Five fruits and vegetables a day? What a joke!
Personally, after the third watermelon, I'm full."
|
|
|
|
|
You need some ASPirin 
|
|
|
|
|
rnbergren wrote: REwriting the entire thing to be `if (blnAdm or blnPL) then`
gesh!
Ctrl-Shift-H, and replace an entire team.
Bidding starts at 40k/annum.
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
I found a very cool library for creating QR Codes[^] from text input.
I decided I wanted to create a DotNet Core (3.1) WebAPI so I could see some (or all) of the QRCoder functionality in action.
However, I run Linux (Ubuntu) exclusively at home and Win10 at work.
The Premise
I wanted to know if I could create a DotNet Core project (using Visual Studio Code) that I could later 1) clone from GitHub (to my Linux box), 2) build and 3) run.
Visual Studio Code
Since it runs on both Win10 and Linux I knew I needed to use Visual Studio Code (instead of plain old Visual Studio). Of course, that also meant I'd need to run dotnet core command line.
I gen'd up a Web API project on the command line following this tutorial[^].
Basically just :
/> dotnet new webapi -o <PROJECT-NAME>
/> cd <PROJECT-NAME>
Then I was able to add the QRCode library from nuget via:
/> dotnet add package QRCoder --version 1.3.6
There was bit of a problem when I went to build, because even though I have dotnet 3.1 installed the qrcoder had a dependency on a newer system.drawing.common. Luckily at Nuget you can click the dependencies tab and see how to get that newer library like:
/> dotnet add package System.Drawing.Common --version 4.7.0
After that, everything built and worked. I added some URLs that allows the user to generate QRCodes as JPGs or as Ascii Text (see below).
Ok, ok, but what about Linux!?!
Building and Running On Linux
I went home, pulled my GitHub repo for the project[^] made sure my dotnet core installation was up to 3.1 and ran:
/> git clone href="https://github.com/raddevus/QRCodeGen"
/> cd QRCodeGen
/> dotnet restore -- restores all required libraries for project
/> dotnet build
/> dotnet run
The web api app started running on localhost:5001 and I made calls into the QRCoder API.
This is where the cross-platform part gets interesting.
Cross-Platform Gets Interesting
Now, think about this. The entire base Web API (built on top of MS libraries) runs and works properly even running on Linux.
The Catch
However, if you attempt to make a call to the QRCoder API that generates the QR Code as a JPG () it has a dependency upon a graphics library which is only compiled for Windows. That causes the QRCoder API to fail when running on Linux.
The error looks like this:
The type initializer for 'Gdip' threw an exception.
---> System.DllNotFoundException: Unable to load shared library 'libgdiplus' or one of its dependencies.
However, since the QRCoder API call that generates the QR Code as ascii (see generated QR Code below - which is all ASCII chars) has no dependency upon Windows methods it succeeds with no problems, even on Linux.
Here's a snapshot of a call to the GetAsciiQR[^] via Linux command-line (curl) with the returned ascii QR code in the command-line window.
You can generate a QR Code with any message you like at my site, just change the value sent in to the API by changing inText in the following URL:
https://newlibre.com/QRCodeGen/QREncoder/GetAsciiQR?inText=try this
You can see the README which will lead you to sample links for all by going to :
https://newlibre.com/QRCodeGen/readme.htm[^]
PS - There's a secret message (all text based) in the QR Code. 
██████████████ ████ ████ ██ ██████████████
██ ██ ████ ██ ██████ ██ ██ ██
██ ██████ ██ ██ ██ ██ ██ ██ ██████ ██
██ ██████ ██ ████ ████████████ ██ ██ ██ ██████ ██
██ ██████ ██ ██ ████ ██████ ████████████ ██ ██████ ██
██ ██ ████████████ ████ ████ ██ ██
██████████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██████████████
██ ████ ████ ██ ██
██ ██████ ██ ██ ████████████ ██ ██ ██
██ ██ ████ ██████ ██████████ ██ ██ ██ ██
██ ██ ████ ██ ████ ████ ██ ████████████ ████
████████ ██ ██████ ████ ████ ████ ██
██ ██████ ████ ██ ████ ██ ██ ██ ██ ████
██ ██ ████ ██████████ ████ ████████ ██ ██████
██ ██████ ████ ████ ██████ ██████ ██████ ██ ████
████ ████ ██████ ████ ██ ████ ██ ██ ██████████
████ ██ ████████ ████████ ████ ██ ████ ████
████ ██ ████ ████ ████ ██████ ██ ██ ████
████ ██ ██ ████ ████ ██ ██ ██ ██ ██
██ ████ ██ ██████ ████ ████ ██████
████ ██ ██ ████ ████ ████ ██████ ████
██ ██ ████ ████ ██ ██████ ████ ████ ████
████ ██ ██████ ██ ████ ████ ██ ██████ ████
██ ████ ██ ████ ██████████████ ████ ████ ████████
████████ ██ ████ ████ ████████████ ████
████ ██████ ██ ██████ ██ ██
██████████████ ████ ██████ ██ ██ ██ ██████ ██
██ ██ ████ ██████ ██████████ ██ ████ ██
██ ██████ ██ ██ ██ ████ ████ ████████████████████
██ ██████ ██ ██ ██ ██ ████ ██ ██ ██████
██ ██████ ██ ██ ██ ██ ██ ██ ████
██ ██ ████ ██████████ ████ ████ ████ ██
██████████████ ████ ████ ██ ██ ████ ████ ██
modified 30-Dec-19 16:08pm.
|
|
|
|
|
Hard .Core again
|
|
|
|
|
Look here[^]
There’s a library you can install to enable System.Drawing on Linux.
What do you get when you cross a joke with a rhetorical question?
The metaphorical solid rear-end expulsions have impacted the metaphorical motorized bladed rotating air movement mechanism.
Do questions with multiple question marks annoy you???
|
|
|
|
|
Brisingr Aerowing wrote: There’s a library you can install to enable System.Drawing on Linux.
That's cool. Thanks for posting. I browsed it and I'll look at it a lot more closely.
|
|
|
|
|
What idiot wrote goto case default instead of goto default in one of my C# switch statements, causing an infinite loop? 
It certainly couldn't have been me. 
For future reference: given:
enum Foo { One, Two } then:
switch (foo)
{
case Foo.One: goto default;
default: Console.WriteLine("Default");
} compiles to:
if (foo != 0) { }
Console.WriteLine("Default"); whereas:
switch (foo)
{
case Foo.One: goto case default;
default: Console.WriteLine("Default");
} compiles to:
if (foo == Foo.One)
{
while (true)
{
}
}
Console.WriteLine("Default");
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
|
A good reason not to use goto.
Social Media - A platform that makes it easier for the crazies to find each other.
Everyone is born right handed. Only the strongest overcome it.
Fight for left-handed rights and hand equality.
|
|
|
|
|
I am seeing an odd performance pattern that does entirely make sense to me. I am not asking for anything to be solved - just a confirmation of my observations, or not.
First, the background : I have tried a few options for a tracing library. Among them were Paul DiLascia's old TraceWin app and library. That worked pretty well and was the last one I used. It had a few drawbacks and the main was performance. I found it took on order of 6mS per message and that is just to slow for me and my app(s). I finally decided to write my own and it is looking really good. I now have overhead of about 3μS per message - yes, microseconds. This is where the weird part comes in.
That is the performance on my main development machine. It is a i9-9900X at 3.5Ghz and it runs W10. My testing machine is a Xeon i7-3820 at 3.6GHz and it runs W7, thank the heavens. The weird part is the Xeon has an overhead of less than 1μS per message, typically right at 0.9 and these numbers are quite repeatable.
My goal was to make this as low-overhead as possible and I think I have succeeded. Each message puts the message's text into a buffer (with sprintf) and then copies the buffer into a piece of shared memory using memcpy. However, first it acquires a mutex that guards access to the shared memory. I would not expect an i7 Xeon to be faster than an i9 Core-series processor at essentially the same clock rate at much of anything and certainly not three times faster. This leads to my main question : has anyone else seen this kind of performance difference accessing kernel-level OS objects between W7 and W10?
As I am writing this, I just thought of a possible explanation : clock throttling. I bet the i9 has its clock throttled back during this test. I will experiment a little and see if that's it.
-edit-
Upon further review, I think that is the explanation. In the task manager it shows the CPU idling at 1.2GHz and this would explain the performance difference. The test doesn't last long enough for the turbo mode to kick in so the CPU stays at its idle clock rate. Oh well.
I guess this means the trace library has a sub 1μ overhead and I am even happier about that. Yee haw.
"They have a consciousness, they have a life, they have a soul! Damn you! Let the rabbits wear glasses! Save our brothers! Can I get an amen?"
modified 18-Dec-19 16:21pm.
|
|
|
|
|
I suppose you speak about c/c++, don't you?
M.D.V. 
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
Rating helpful answers is nice, but saying thanks can be even nicer.
|
|
|
|
|
The library I made is in c++.
"They have a consciousness, they have a life, they have a soul! Damn you! Let the rabbits wear glasses! Save our brothers! Can I get an amen?"
|
|
|
|
|
Any chance to publish an article about it?
M.D.V.
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
Rating helpful answers is nice, but saying thanks can be even nicer.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
