Slashdot is powered by your submissions, so send in your scoop


Forgot your password?

Comment: Re: Call me conervative, but (Score 1) 41

by TheRaven64 (#48674631) Attached to: The World of YouTube Bubble Sort Algorithm Dancing
Insertion sort is terrible for the use cases the grandparent described. For one thing, it requires allocating a new data structure for storing the data (an immediate disqualification for a lot of embedded tasks). Second, it has much worse cache interaction because it requires searching the second array. Assuming that your target is an array, then it also requires a bit memcpy for each insert, which means that it likely requires a similar number of memory operations to the bubblesort, but with more temporaries. You can do a bubblesort in-place, with good cache locality, and only a handful of registers (insert base, top, current, and two for holding the current elements). If your CPU has 8 GPRs then the space requirements of a bubblesort are effectively zero - no memory required.

Comment: Re:Bogus algorithm (Score 1) 41

by TheRaven64 (#48674619) Attached to: The World of YouTube Bubble Sort Algorithm Dancing
Insertion sort is one of these good-on-paper algorithms. It's very fast if insertion is cheap. But insertion relies copying unless your data structure is a linked list. If it's an array (worse, a contiguous on-disk store) then that copying can be very expensive. If it is a linked list, then you're going to have very expensive search (sure, you may still be O(log(n)), but that constant multiple is going to be hurt by the fact that you're hammering your cache and killing your branch predictor).

Teaching algorithms separately from data structures is one of the biggest flaws in modern computer science education. It's impossible to reason sensibly about one without the other.

Comment: Re:Bogus algorithm (Score 1) 41

by TheRaven64 (#48674613) Attached to: The World of YouTube Bubble Sort Algorithm Dancing
Bubblesort has two advantages. The first is that, because it's only swapping adjacent elements, it has very good locality of reference (which means better cache usage, but can also mean more amenable to fine-grained locking). The second is that it performs well on almost-sorted data (that O(n^2) is the worst case - it's closer to O(n) if your inputs are mostly sorted). These two mean that there are situations where bubblesort can be useful, though they're quite rare.

Comment: Re:The Navy sucks at negotiating (Score 1) 93

by TheRaven64 (#48674589) Attached to: US Navy Sells 'Top Gun' Aircraft Carrier For One Penny

And what was the destructive capacity of the Navy in 2006 compared to August 1945? Hell, one Ohio class submarine has more destructive capacity than the entire Navy from 1945

A statistic that floated around earlier in the year when Argentina was grumbling about the Falklands again: one of the battleships that the British were sending to the area could fire, in one minute, more munitions than were fired in the entire 1982 conflict. I'd imagine that the differences between 1945 and now are even more pronounced.

One constant trend has been that soldiers are less expendable. In the first world war, sending men to walk slowly towards machine guns and throw a grenade if they survived to get close enough was their patriotic duty. By Vietnam, having large numbers of soldiers come back in body bags was politically unacceptable.

In the 1940s, Japan was flying aircraft loaded with bombs into American warships. A few years later, people realised that you could design aircraft for this purpose and make them a lot lighter and able to accelerate more if you removed the human pilot. They called them anti-ship missiles.

The fighter screen that fleets needed to protect themselves from aircraft in the '40s is now replaced by anti-aircraft and interceptor missiles (and dumb projectiles). In the next generation of ships a lot of this will be replaced by lasers, which reduces some of the resupply need (you can't run out of laser ammunition on a nuclear carrier unless your ship is so badly damaged that it's not a good idea to be anywhere near it).

Gradually, a lot of the roles for aircraft are being replaced by drones, which means that you need smaller carriers. They don't need to house as many pilots, they don't need as many support staff.

Another part of this trend is to replace reusable vehicles with single-use munitions. Fighters are more expensive than missiles, so you spend a lot on maintaining them. Drones are a lot cheaper, so you can afford to fly them for a couple of missions and then scrap them (explosively, near someone you don't like).

Comparing numbers, as the grandparent did, is completely meaningless. You may as well compare the size of the air force to the number of soldiers Napoleon had.

Comment: Re: The Interview hits warez sites (Score 1) 143

There are basically only three decoders that cover most of the market: Microsoft's DirectShow filter, libavcodec / libavformat, and QuickTime. Hardware decode doesn't help much, because you still have the same software path as everyone else doing the de-encapsulation and file parsing, which is where the exploitable bugs often show up. If you have vulnerabilities in each of these then it's not generally hard to hide them all in the same file, as the codecs aim to be resilient to corrupted data so will usually just drop a frame or two for the exploits aimed at the other implementations.

Oh, and libavcodec / libavformat are used in Android (and in a lot of iOS apps, as AVFoundation doesn't always expose useful APIs), as well as in desktop browsers, so they're a pretty good target to aim for.

Comment: Re: Yes, it's in FB's "ordinary [business] course" (Score 2) 43

by TheRaven64 (#48674547) Attached to: Federal Judge: Facebook Must Face Suit For Scanning Messages
People who think a fake name on Facebook protects them from any of the privacy invasion really haven't been paying attention to the last decade of data mining. The reason Facebook no longer cares if you register with a fake name is that they've been able, with very high accuracy, to get your real name and address without your providing it for a few years.

Comment: Re: The Interview hits warez sites (Score 4, Informative) 143

What secure OS do you run where the video codecs have had a full security review? Google found (and fixed) around 300 exploitable holes in libavcodec / libavformat in the last year. Do you want to bet that they found them all? Do you always run video codecs in an unprivileged process?

Whom computers would destroy, they must first drive mad.