问:
More efficient alternative that checks if a list can be made a palindrome
For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm:

```<code>def algo_X(A):
    i = 0
    j = len(A)-1
    while i < j:
        if A[i] != A[j]:
            k = i + 1
            while k < j:
                if A[i] == A[k]:
                    A[k], A[j] = A[j], A[k]
                    break
                elif A[j] == A[k]:
                    A[k], A[i] = A[i], A[k]
                    break
                else:
                    k += 1
            if k == j:
                return False
        i += 1
        j -= 1
    return True
</code>```

This algorithm returns True if the elements of list passed as argument can be manipulated (swapped) in order to create a new list, which, if we read from the left or from the right, has the same order of elements (palindrome). Else returns False.
For example, this list ['a', 'a', 'b', '2', 'b', 'b', ‘2’] can be ordered so that we have a list with the same elements in the same positions, if we read at the same time from the left and from the right: ['a', 'b', '2', 'b', '2', 'b', ‘a’].

Note that this is my interpretation of the algorithm, they did not tell us what this algorithm was supposed to do.

If I am not wrong, this algorithm, in the worst case (and average case), is O(n2), and Ɵ(n) in the best case.

The exercise specifically states that I don't have necessarily to change the list (like in algo_X), but just to return True or False specifying respectively if the list can be made a palindrome or not.

We cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don't "know" exactly the time complexity of those functions. I will edit my question

To make a better algorithm for the worst case, I thought I could use merge sort, whose time complexity is always n*log(n), plus a loop, which would not make the algorithm worse, asymptotically.

This is my merge function for my merge sort function:

```<code>def merge(A, B):
    ls = []
    a, b = 0, 0
    while a < len(A) and b < len(B):
        if A[a] <= B[b]:
            ls.append(A[a])
            a += 1
        else:
            ls.append(B[b])
            b += 1
    while a < len(A):
        ls.append(A[a])
        a += 1
    while b < len(B):
        ls.append(B[b])
        b += 1
    return ls
</code>```

This is my merge sort function:

```<code>def merge_sort(A):
    if len(A) < 2:  # basic condition
        return A
    L = merge_sort(A[0:len(A)//2])
    R = merge_sort(A[len(A)//2:])
    return merge(L, R)
</code>```

Finally, here's my alternative, which returns True, if the list can be made a palindrome, False otherwise:

```<code>def better_algo_x(A):
    if len(A) < 2:
        return True
    sorted_A = merge_sort(A)
    odd_groups = 0
    current = sorted_A[0]
    c = 1  # Used to count the number of characters that are equal between them
    for i in range(1, len(sorted_A)):
        if current == sorted_A[i]:
            c += 1
        else:
            if c % 2 == 1:
                odd_groups += 1
            if odd_groups > 1:
                return False
            current = sorted_A[i]
            c = 1
    # for the last group of characters
    if c % 2 == 1:
        odd_groups += 1
    if odd_groups > 1:
        return False
    return True
</code>```

I have a few questions:

Are my functions correct?

Is my analysis of the time complexity of the algorithm algo_X correct?

Does my better_algo_x do what it is supposed to do?

Does it do it in n*log(n) in the worst case?

Can I still improve it? How?

Do you know (other) better alternatives for algo_X?

Of course, some questions might seem silly, but I would like to hear the opinion of some experts. Of course, I have tried my algorithms.

答:
Yes, your analysis and algorithms are correct. But it can be made better by trading off memory for performance IF the amount of possible characters in string is limited (eg. it is not full Unicode). Basically, you can use hash-map to keep count of every character in O(n)*O(1) and then go through the list in O(1) (because the count of all possible characters is always the same). Meaning O(n)*O(1)+O(1) = O(n) in worst case.</p>

```<code>def isPalindromic(A):
    hashArray = array.array('I', [0] * 256)

    for ch in A:
        ascii = ord(ch)
        hashArray[ascii] += 1

    notEven = 0
    for count in hashArray:
        if (count > 0 and count % 2 == 1):
            notEven += 1

    return notEven <= 1 #one can be even, then it will be in the center
</code>```

Body:
Yes, your analysis and algorithms are correct. But it can be made better by trading off memory for performance IF the amount of possible characters in string is limited (eg. it is not full Unicode). Basically, you can use hash-map to keep count of every character in O(n)*O(1) and then go through the list in O(1) (because the count of all possible characters is always the same). Meaning O(n)*O(1)+O(1) = O(n) in worst case.

def isPalindromic(A):
    hashArray = array.array('I', [0] * 256)

    for ch in A:
        ascii = ord(ch)
        hashArray[ascii] += 1

    notEven = 0
    for count in hashArray:
        if (count > 0 and count % 2 == 1):
            notEven += 1

    return notEven <= 1 #one can be even, then it will be in the center


问:
Is using triggers best solution for this scenario
A large SQL transactional database has more than 100 tables (and it will grow). One of them is called Order. Then, there is another table WorkLoad which derives from Order and many other joined table which contains a list of all active order. Every time an order record is created, if it meets certain conditions, it should be instantly inserted into WorkLoad table. And finally, there is a third table WorkLoadAggregation which displays aggregated data grouped by date and shop and it is completely built from WorkLoad table. WorkLoadAggregation should also display live data meaning that if a record is inserted in WorkLoad table then matching date/shop aggregation should also be updated.

My idea was to handle this by triggers:

When record is inserted in Order table, trigger calls stored procedure which inserts record into WorkLoad table

When Order record is deleted trigger deletes the record from WorkLoad table

When Order record is updated in a way that it doesn't meet WorkLoad conditions, trigger deletes the record from WorkLoad table

When record is inserted/deleted/updated in WorkLoad table, trigger calls stored procedure which updates matching date/shop aggregated record in WorkLoadAggregation table

I haven't used triggers that much in such large transaction dbs and for such frequent calls. Is there anything bad in this approach? My biggest concern is usage of "chained triggers", meaning that trigger on one table activates trigger on another table. I've been reading few articles which state that developers should be very cautious when using triggers. Are there any better solutions? Should I consider any NoSQL solution?

答:
I suggest that u should follow what thomas Stringer suggested in comments.

Use store-procedures to insert update and delete from order table. In that you can call any of your tables simultaneously along with the query data and perform your transactions.

Learn more about MS-SQL Store-procedures HERE

ContentLicense: CC BY-SA 3.0


问:
What's the algorithm should I use for seeing how well 2 strings match?
Suppose I have 2 strings:

```<code>string1 = "home/lisa/Music/some_files/01.05 - Garden Ground.mp3"
string2 = "Music/Jim Smith/Unknown/(Deluxe Version/Garden Ground).mp3"
string4 = "Music/Jim Smith/Unknown/00 - Garden Ground.mp3"
</code>```

Basically, I want to know if string 2 contains the same mp3 file as string 1.  In the above example, you can see this is the case with Garden Ground.mp3.  What's the best way to go about this?  Should I try Levenshtein distance?    I thought about doing a regular expression, but there's no guarantee string 2 will be formatted with parentheses in the exact same place every time.  In fact, string 2 could look like string 4, for example.

答:
I don't really think any existing algorithm is going to work in your case. In your case, you are not looking for similarity between strings, but if strings contain similar values. Levenstein distance is about similarity of strings, not if strings contain similar values.

In your case, the simplest algorithm would be (pseudocode).

Get name of each file without directory (I'm assuming directory doesn't matter)

Split each name into words based on predefined separators (' ', '-', ';', '.', etc.. you have to do some trial-and-error here to find the right separators)

Compare how many words are same between two names (eg, in your case there are 2 same words between each of the files)

If the count of same words exceeds some threshold, consider them same

The last step is obviously the hardest one. Figuring the threshold to minimize false positives and negatives is quite a challenge. The simplest is absolute threshold (eg. count >= 2 would match your case), but it might not be enough. Relative threshold (eg. count / totalWordsCount > 50%) might work, but it is harder to test and highly depends on what separators you pick.


问:
To One Repository or Two
I have a C codebase which supports a number of build personalities, for a given board architecture. It's mostly in maintenance mode. We don't do new active development on it.

We have a new board for a generation 2 of the product. Generation 2 will replace generation 1 (we aren't making any more Gen 1 boards). Generation 2 will require a good chunk of the code to be rewritten completely. I'd say 50% of it. OTOH, there is some code that will just stay the same. Making the build modular to support both types isn't worth it to us. So we're essentially going to permanently fork the project into two.

I'm soliciting input on whether to just

Make a new git repository, copy the code from the old into it and take off and see where the future takes us.

Keep the same repository, but just add more branches.

We currently use a scheme in our repository of having a master branch for production releases, a testing branch where we accumulate "blessed" work, and individual branches for different units of work we do.

The Pros/Cons as I see them are:

Two Repositories

Pros: Branches stay simple. Forced to have a repository for each loaded if I need to compare

Cons: Can't cherry pick between the two (we rarely do this though)

One Repository, Different Branches

Pros: Code all stays in same branch, maybe able to leverage some "cross branch" features of git

Cons: Have to annotate the master and testing branches for the two different things to disambiguate them

Which should we do, and why?

答:
Because git is so flexible, you could probably do fine either way, and which one is the more correct answer depends entirely on what your day-to-day workflow is like, so I'll give the answer for the workflow I'm used to (which I think is one of the "normal" ones).

Most of the time I'm typing a git command or figuring out what git command to type, one of the big assumptions I'm always making is: "There is only one branch with 'real' code (code that rolls out to production and makes the business money), and it is master; all other code is not 'real' until its branch passes code review and is merged into master." Although git in no way requires you to make this assumption, I think that's how a lot of real-world development works.

The single repository option essentially means you have a repo with "two master branches". Unless you plan to be developing and delivering two different products in parallel that share a lot of code (which in this case you aren't), I think that's a little bit unintuitive and error-prone compared to giving each product a separate repo. Personally, I know I'd always be slightly worried about merging something into "the wrong master branch" by accident if my team did this.

Also, as amon said, git does not stop you from moving code between repos. A few git fetch and git cherry-pick commands should be all you need to apply "old" commits to "new" code branches. It's not much harder than moving things around within a single repo. It'll feel different, but it probably should feel different.

Title: To One Repository or Two


问:
How is the UnitOfWork pattern related to Monadic programming?
Looking over the definition of the Unit of Work pattern it seems very much like what a programmer would get if they implemented a Monad such as an IO or Transaction Monad.  What makes the unit of work concept fundamentally different from the use of a Monad?  Assume that we are working in a language that has enough power to implement most common Monads fully and can implement a unit of work pattern similar to what you may find in Java or C#, especially one with a type system such as Scala's or Haskell's.

If one can be chosen over the other what are the pros and cons of each approach?

答:
Your question is a little odd, sort of like asking why you need the unit of work pattern when you could just use objects.  Monads are more fundamental than your question implies.  You can use a monad as part of the implementation of the unit of work pattern, but that's not a sufficient description of the solution.  You would also need to describe which monad to use, the type parameters used, how to initialize it, how to implement a step, and what to do with the result.

A transaction monad indeed looks like it might be a relatively good building block to implement this pattern, but perhaps a new monad specifically created and tailored for implementing unit of work would be cleaner.

However, part of the benefit of the unit of work pattern is that it helps gather database updates from scattered places in your code.  Monads have the annoying property that they want to be already gathered.  If you have to gather your database update code into one place anyway, there might be a simpler way to aggregate it.


问:
Observer pattern without state change?
My question is whether there is a similar pattern to Observer that does not imply a state change in the observed object. The following is a concrete example:

I have a ConnectionFactory class which is responsible for creating JDBC database connections. Now I have the need to do something with every connection right after it has been created (specifically, I need to set a user-defined variable in the MySQL session) but I don't want to do it in the ConnectionFactory class since I feel this is something that goes beyond its responsibilities.

I have considered making ConnectionFactory extend java.util.Observable and having an Observer class that will be notified every time a connection is created. However it seems that this approach is incorrect, since the Observer pattern implies that the observed object is being observed for state changes, but the state of ConnectionFactory does not change at all when a connection is created.

As you can see, I have to go around this issue by simulating a state change before calling notifyObservers() (otherwise the observers will not be notified) and synchronizing those two statements in order to make sure that the "state changed" flag set in the first statement is still active when the second statement is executed. This kind of workaround just increases my suspicion that I have taken the wrong approach.

```<code>public class ConnectionFactory extends java.util.Observable {

    public static final ConnectionFactory INSTANCE = new ConnectionFactory();

    private ConnectionFactory(){};

    public Connection makeConnection(){

        Connection connection = null;

        // ... obtain the connection ...

        synchronized(this) {
            this.setChanged();
            this.notifyObservers(connection);
        }

        return connection;
    }
}
</code>```

```<code>public class Foo implements java.util.Observer {

    @Override
    public void update(Observable o, Object arg) {

        Connection con = (Connection)arg;

        // ... set MySQL user-defined variables ...

    }
}
</code>```

```<code>// Somewhere in initialization code...
ConnectionFactory.INSTANCE.addObserver(new Foo());
</code>```

So there is an object that I want to observe, there is a class that must do something when the observed object fires certain events, but those events are not state changes. If the Observer pattern is not applicable, then what would be a correct approach?

答:
You can:

Use the features of Observer that you need, and ignore the other features; or

Use some other software pattern that more closely matches what you need, or

Don't use a pattern at all, and simply write code that solves the problem.

Just because the Wikipedia article says that the Observer pattern is designed to notify the observer of state changes doesn't mean that's how you have to use it, though I would argue that any event that occurs in an otherwise immutable program is a state change.

Programmers tend to be obsessed with being "correct."  Don't.  At the end of the day, word definitions don't matter; what matters is that your program works.

Title: Observer pattern without state change?


问:
Working on Free Software
My main experience is with iOS, but I'd like to move into writing free and open source software instead. Are there many jobs out there that allow you to work on projects like this? I've looked on the FSF website among others, but I'm having trouble finding any.

Are there certain communities or organisations that I would benefit from joining? And are there certain areas of the world that favour this kind of work?

This is something that I really want to do, but I'm not sure how to get started. Any advice would be much appreciated.

答:
Your question looks like career advice so might be off-topic here.

I am sometimes working on free software, but I am not an expert on that.

First, most major (or large and significant) free software (Linux kernel, GCC compiler, Firefox browser) are mostly (but not entirely) developed by paid professionals. In other words, the idea that major free software is developed by part-time hobbyists is today mostly a myth (it might be still true for many one-man  projects; it is false for multi-million lines of source code free
software). Free software is very serious business.

Then, as a job market, the free software communities are very demanding and extremely competitive (world-wide). You are unlikely (IMHO) to find a paid job if you are not known by some free software meritocracy.

Hence my advice is to start working on your own on some existing free software project you like (you probably could check that your work contract does not legally prohibit that). Once you are known for some positive contributions to some free software things might become different. Contributing to free software (in a regular and transparent manner) require both technical skills (understanding the code base) and social skills (interacting with the community).

BTW, things are different if your are employed by some corporation, or if you are self-employed. Several free-lancers are able to sell some part-time contributions to free software. Several corporations permit some workers to work on some free software part-time.

So you could start today by finding some interesting (for you!) free software, e.g. on github, then contributing some code to it.

Title: Working on Free Software


问:
Does making source code available affect your ability to generate revenue?
We’re working on a .Net framework which ultimately amounts to a single DLL.  We intend to charge for commercial use of the framework, but make it free for open source/non-commercial use.  The rough plan at the moment is to administer this through some form of fairly simple licence which will be issued whether you’re using it for free or paying.

We’re debating whether to make the source code available.  It’s our perception (and our own preference) that it’s far more appealing to use something where you have access to the source code.

I’m interested in whether people think making the source code available will damage our ability to make money from the framework, or whether it will encourage more usage and enough “good” people will arrange to pay for the correct licence if using it commercially.

My feeling is that, generally, commercial operations don’t mess about on the licencing front and so making the source code available will only encourage usage and therefore ultimately generate more revenue, but I’d be interested in others views/experience.

答:
If it is a managed .NET framework, people can use Reflector to look at the source code anyway.

I've seen a number of companies that appear to work this dual-licensing model successfully.  Having access to the source code doesn't necessarily mean that people will steal the code. Personally, I would rather be properly licensed, as has any company I have ever worked for.  But having access to the source code can encourage people to try your product out.

There's something about having access to the source that feels like a security blanket; you know that you will probably never need it, but if you spend many man-hours worth of effort committing to a third-party library, it's good to know you can dig into the code and fix something if you ever get into a bind, or the original author of the code gets thrown under a bus.

ContentLicense: CC BY-SA 2.5


问:
component-based power system for a game
My issue is that I've been trying to implement a power/electrical system for a while now. I'm using Unreal Engine 4 with C++ but that's not really relevant.

I'm trying to implement some sort of system of generators, power storage, and power draining objects that all interact through one another through a system of wires or cables, similar to any of the many minecraft mods which add machines.

My thoughts were moving towards using a node system, where nodes looking for power can trace through the system and find a generator or storage cell. I couldn't find a single tutorial or example anywhere online. Anyone have any input?

Thanks!

答:
After experimenting for a while I have a solution. I've split the network of machines into many EnergyNet objects, which represents something like a cluster of wires. Each EnergyNet represents a system of energy suppliers, consumers, and storagers, which are a combination of both.

Every update tick, the energy net measures the amount of energy produces and distributes it to the consumers. Any remaining energy is then stored in the storagers or disposed.

By using multiple EnergyNets, I can create many complex systems with far distanced between them. If two EnergyNets were to intersect, I could easily merge their components the for a single EnergyNet!

edit:
I represent the machines by a

```<code>List<Machine>
</code>```

and my connections by a

```<code>List<Tuple<Machine, Machine>>
</code>```

If anyone would like, I can submit my source code, but I have to admit it's a bit of a mess. I planned on rewriting everything once I had figured it out...

Title: component-based power system for a game

Body:
After experimenting for a while I have a solution. I've split the network of machines into many EnergyNet objects, which represents something like a cluster of wires. Each EnergyNet represents a system of energy suppliers, consumers, and storagers, which are a combination of both.

Every update tick, the energy net measures the amount of energy produces and distributes it to the consumers. Any remaining energy is then stored in the storagers or disposed.

By using multiple EnergyNets, I can create many complex systems with far distanced between them. If two EnergyNets were to intersect, I could easily merge their components the for a single EnergyNet!

edit:
I represent the machines by a

List<Machine>

and my connections by a

List<Tuple<Machine, Machine>>

If anyone would like, I can submit my source code, but I have to admit it's a bit of a mess. I planned on rewriting everything once I had figured it out...


问:
Counting digits of a decimal number
Is there an algorithm to count digits of a decimal number other than saving it as a string and then looping to find the decimal point and thus count the digits?</p>

答:
You have options:

Take the absolute value of the number, now it is positive.

Then turn it into a string.

Then find the "." by searching for the "." by using a string function or by looking one character at a time.

Or you can try:

Take the absolute value of the number.

Use the log function, which might be in a math library. You don't want the natural log, you want the base ten version of a log.

Truncate the answer from the log and add 1. Now you have the number of chars to the left of the decimal point.

or you can try:

Take the absolute value of the number.

Truncate the number. This throw away everything to the right.

Turn the result into a sting

get the length of the string.

which is faster? which is easier to understand?

Try one, make test cases, time it; then move to the next one.

Research why taking the absolute value is important.

Title: Counting digits of a decimal number


答:
I know what you are thinking.  You are thinking that if you could somehow enumerate the digits after the decimal point, you could count them.  But whether you use a string or any other mechanism, there is a fundamental problem:

how do you know when to stop counting?

Converting the number to a string might sound like an easy solution, but that's only because someone else has already made this fundamental decision for you, and their choice has a rather slim chance of being the right choice for you.  If you ask for a string representation of π (happy π day, by the way!) you will obviously get a finite length string, which might tempt you to believe that π has a finite number of digits.

Not.

So, what you are trying to do will not work,  because there are many numbers that cannot be accurately represented using either floats or doubles, so such numbers appear to contain meaningless decimal digits which only end there where the precision of the float or double ends.  Please do try this at home: printf( "%.30f\n", 2.9f ); the result will be something funny, like 2.900000095367431640625000000000 or 2.899999999999999911182158029987, or similar depending on your machine and compiler.

And of course, this will easily manifest itself in calculations: if you divide 29 by 10 you will not really get 2.9, but an approximation of it.

So, whatever you think you are going to accomplish by counting the decimal digits of a number will not work.  You have some other kind of problem to solve, and you think that counting decimal digits will solve it, and you have come here to ask us how to implement your imaginary solution.  This is a typical instance of asking an answer instead of asking a question. It is nothing to be ashamed of, lots of people make this mistake on stack exchange, but my point here is that you better find a way to solve your original problem which does not involve counting the decimal digits of a number.

Title: Counting digits of a decimal number

Body: Is there an algorithm to count digits of a decimal number other than saving it as a string and then looping to find the decimal point and thus count the digits?</p>


问:
How do you iterate through an array and delete an element?
I have an array and I can iterate through it. I know that it is impossible to change the size of an array; however, how do I take out a certain element that I not want in the array anymore?

Example: if the user chooses to delete the certain element how do I go about writing this out in my code?

答:
The Java Collections framework is something that you should browse.  There are also some types that aren't array-like (Set and Map) but you will find that you will use them often.  There are many different types of collections, and some have advantages over others for certain types of operations.

Classic arrays

First, the thing that isn't in the collections framework.  The Array.  Not ArrayList, but rather the classic int[].  The advantage of the array is that it closely maps to what memory is.  foo[42] is to lookup.  Many system level calls that give you a fixed number of items are arrays and they are good to know.  "1,2,3".split(",") returns back an array for example.

The problem with arrays is that they aren't that flexible.  Adding an element to the end of an array that already is at is maximum capacity means allocating a new, larger array and then doing an System.arraycopy() (javadoc) to copy all the elements from one array to another array in a timely manner.

To remove an element from the list you need to remove it and then walk the remainder of the list to have everything be contagious again.  If you want to remove foo[4] from the list, you then assign foo[4] = foo[5] and foo[5] = foo[6] and so on down to the end of the list.  Thats if you have to do it by hand.  You can also use that System.arraycopy mentioned to do it for you given the right set of arguments.  Something like:

```<code>System.arraycopy(foo,5,foo,4,foo.length - 4);
</code>```

I might have that wrong, but thats the general idea.  Copying the array back on itself.  It should work.

If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array.

Lists

As you see, arrays are a bit awkward to work with.  You've got do it all by hand.  Its good to know, but a pain to practice.  There are two lists that are in common use that make this easier for you.  For the most part, Lists look like arrays.

```<code>List<Integer> foo = ...;
foo.get(4);
foo.remove(5);
</code>```

You call methods on them, but you are fetching the 4th element via method call instead of via direct access through the array.  See that foo.remove(5).  Thats it.  You're done. You have removed an element from the list and deleted it. Much easier to remember.

ArrayList

The ArrayList is backed by an Array.  This means that doing foo.get(4) runs fast, but foo.add(42, foo.size()+1) is likely to be slow because it has to do all of that moving of things around to allocate a new list (yes, I know that the list can be longer than the size, but lets assume that its the same size as its actual list).

Instead of having to remember how to do all the shuffling, you've got nice methods to do your work for you.  It doesn't mean that its not done (the work is still done behind the scenes of the interface), but its something that you don't have to worry about.

So, the ArrayList is for:

fast get (O(1))

slow remove and insert (O(length))

slow append when full (O(length))

LinkedList

For some reason, everyone's goto list implementation is the ArrayList.  I don't know why. Many times when I'm working with Lists, the LinkedList is the one that is more applicable.  You keep adding things to the end.  Rarely do you want the nth element.  You just want to iterate over them.

This is what the LinkedList is good for.  It does fast remove and append and its iterator is just as fast as the ArrayList.  Its just if you want foo.get(400) its going to be a bit slower than the ArrayList implement.

The LinkedList is also a Deque too, but people forget about that.  That lets you access the LinkedList as a double ended queue (nice for implementing a Stack or Queue).

So, if you are just appending and iterating, the LinkedList is for you.

Get is slowish (O(index))

Fast append (O(1))

Remove and insert is slowish (O(index))

Note that the O(index) there is a bit of an award bit.  It will index depending on which way is faster to get there (from the end or start).  So if the LinkedList is 100 long, and you get(10), it starts from the start.  If you ask for get(90), it starts from the end. So get(index) is never more than get(length/2), but thats all just factors that don't matter when looking at Big O.

Body:
The Java Collections framework is something that you should browse.  There are also some types that aren't array-like (Set and Map) but you will find that you will use them often.  There are many different types of collections, and some have advantages over others for certain types of operations.

Classic arrays

First, the thing that isn't in the collections framework.  The Array.  Not ArrayList, but rather the classic int[].  The advantage of the array is that it closely maps to what memory is.  foo[42] is to lookup.  Many system level calls that give you a fixed number of items are arrays and they are good to know.  "1,2,3".split(",") returns back an array for example.

The problem with arrays is that they aren't that flexible.  Adding an element to the end of an array that already is at is maximum capacity means allocating a new, larger array and then doing an System.arraycopy() (javadoc) to copy all the elements from one array to another array in a timely manner.

To remove an element from the list you need to remove it and then walk the remainder of the list to have everything be contagious again.  If you want to remove foo[4] from the list, you then assign foo[4] = foo[5] and foo[5] = foo[6] and so on down to the end of the list.  Thats if you have to do it by hand.  You can also use that System.arraycopy mentioned to do it for you given the right set of arguments.  Something like:

System.arraycopy(foo,5,foo,4,foo.length - 4);

I might have that wrong, but thats the general idea.  Copying the array back on itself.  It should work.

If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array.

Lists

As you see, arrays are a bit awkward to work with.  You've got do it all by hand.  Its good to know, but a pain to practice.  There are two lists that are in common use that make this easier for you.  For the most part, Lists look like arrays.

List<Integer> foo = ...;
foo.get(4);
foo.remove(5);

You call methods on them, but you are fetching the 4th element via method call instead of via direct access through the array.  See that foo.remove(5).  Thats it.  You're done. You have removed an element from the list and deleted it. Much easier to remember.

ArrayList

The ArrayList is backed by an Array.  This means that doing foo.get(4) runs fast, but foo.add(42, foo.size()+1) is likely to be slow because it has to do all of that moving of things around to allocate a new list (yes, I know that the list can be longer than the size, but lets assume that its the same size as its actual list).

Instead of having to remember how to do all the shuffling, you've got nice methods to do your work for you.  It doesn't mean that its not done (the work is still done behind the scenes of the interface), but its something that you don't have to worry about.

So, the ArrayList is for:

fast get (O(1))

slow remove and insert (O(length))

slow append when full (O(length))

LinkedList

For some reason, everyone's goto list implementation is the ArrayList.  I don't know why. Many times when I'm working with Lists, the LinkedList is the one that is more applicable.  You keep adding things to the end.  Rarely do you want the nth element.  You just want to iterate over them.

This is what the LinkedList is good for.  It does fast remove and append and its iterator is just as fast as the ArrayList.  Its just if you want foo.get(400) its going to be a bit slower than the ArrayList implement.

The LinkedList is also a Deque too, but people forget about that.  That lets you access the LinkedList as a double ended queue (nice for implementing a Stack or Queue).

So, if you are just appending and iterating, the LinkedList is for you.

Get is slowish (O(index))

Fast append (O(1))

Remove and insert is slowish (O(index))

Note that the O(index) there is a bit of an award bit.  It will index depending on which way is faster to get there (from the end or start).  So if the LinkedList is 100 long, and you get(10), it starts from the start.  If you ask for get(90), it starts from the end. So get(index) is never more than get(length/2), but thats all just factors that don't matter when looking at Big O.


答:
If it is an array of reference types, then the contents of each cell will default to null.  If you have placed a real value in a cell, you can effectively "delete" it by replacing it with null.  As long as your code checks for null values, then replacing with null can count as a deletion.  But this is an inefficient use of arrays, whose primary advantage is speed in accessing indexed values whose number does not change.  If your "collection" may or not contain certain values then a map or list would be better.

If it is an array of primitives (int, byte and so on) then you cannot delete contents.  You could insert the default value (0 for numeric types, false for booleans) but that probably is not useful to you.  The best you can do is copy all elements apart from that one into a new array.  Something you could also do for reference types by copying everything that isn't null.

So the important question is this:

Do you want to know whether a specific array index contains a meaningful value?

Or are you simply interested in all the values currently in the array?

If the answer is 1, then for primitive types the answer is no.  For reference types you could replace them with null, but really, a map would be better because then you can delete the key.

If the answer is 2, then you can copy all the other cells into a new array.

So which is it?

Title: How do you iterate through an array and delete an element?

Body:
I have an array and I can iterate through it. I know that it is impossible to change the size of an array; however, how do I take out a certain element that I not want in the array anymore?

Example: if the user chooses to delete the certain element how do I go about writing this out in my code?


答:
If you must really do this using an array, then you will need to:

copy all elements of the array after the element being deleted down by one position to cover the removed element.

resize your array to be smaller by one element.

Copying elements down by one position can be done either by writing a loop yourself, or by invoking System.arraycopy( src, srcPos, dest, destPos, length).

Resizing the array can be done like this: myArray = Arrays.copyOf( myArray, newCapacity ).

That having been said, if you have any need to manipulate the length of the array, then definitely go with ArrayList instead of using arrays. This wheel has already been invented.


问:
Extracting client specific code. refactoring possibilities required
I am facing a Design problem. I have a set of classes which writes data in XML,JSON or HTML formates for different clients.

I have a class which receives Data and a XML, JSON or HTML writer as it parameter.

And these Writer have a common Interface, Writer uses the Data to create Data in speficied format. The writes have methods like writeHead, writeBody, WriteImages, writeFooter, writeDescriptions

Now my problem is that Descriptions part of the Documents is very client specific. Only that specific part looks completly different for each client but the rest of the Document is same.

Should I use writeDescriptions as a factory which calls clientSpefic writeDescriptions function? then I have another problem that I have many different formates like JSON,HTML,XML....

What will be the best possible way to hanlde is sitution?

答:
Now my problem is that Descriptions part of the Documents is very client specific. Only that specific part looks completly different for each client but the rest of the Document is same.

Should I use writeDescriptions as a factory which calls clientSpefic writeDescriptions function? then I have another problem that I have many different formates like JSON,HTML,XML....

A factory as you described is a reasonable approach to resolving this problem.  There's no getting around the fact that each client has their own format for the description, so hide that implementation detail behind the writeDescriptions method as you described.

Given that you have multiple output formats (JSON, HTML, ...) then you'll need to pass that information along so that writeDescriptions can make the appropriate decision.

If possible, consider writing the client specific stuff to a "universal format" and then have writeDescriptions make a call to a formatter for the output function (ie. it translates from the "universal format" to the specific output format).  That way you don't have to repeat output functionality across the different client implementations.

Additional thought: It's possible you may run into a problem using a factory pattern like this, but it's a fairly typical usage.  Don't worry about those future problems until they actually occur.  At that point, you have a new design question to the effect of "I had XYZ problem and solved with a factory.  The factory introduced ABC problem.  How should I resolve?"


问:
Do bare computer systems (without OS installed) use (executable) files?

As far as I read, files are introduced in OS books. Before an OS is installed on a bare computer system, does the computer use files?

In particular, executable files have formats in OSes, e.g. executable files have ELF format in Linux, which can guide the loader in the OS to load them into memory when running them. Before installation of an OS, does the computer system have the concept of executable files or something similar for storing programs?

If so, what is their format, for example, on a X86 or X86-64 bit bare computer machine?

Thanks.

I am not asking about booting but I am curious how a program is stored on a bare computer. A program may be for booting or not for booting. In particular, I am interested in how a user program is stored on a bare computer.

答:
To get an OS up and running, there are various things being executed which are typically called "loaders" and "bootstrappers".

Their collective purpose is exactly as their names imply: to get the OS up and running, one step at a time.

Some of these executable code are stored in read-only memory (ROM), or some type of reprogrammable memory (such as Flash ROM), or a certain predetermined location on the storage disk (located on a so-called "boot sector", which is a predetermined location on a "disk partition") from which the machine can be started up.

Your suspicion that at least some of these executable code must exist outside the concept we call "files" or "file system" is correct. Not all of them are; but at least some of them must be.

The computer hardware-firmware, and operating system itself typically are able to access these "non-file" storage areas to perform infrequent maintenance upgrades to these executable code.

The purpose of allowing these upgrades from software is an engineering choice driven by the consumer market - it is cheaper to maintain computers if is it possible for customers to perform the upgrades, than to require machines to be shipped back to a factory or maintenance center to do the same.

Are these executable code different from the code found in "executable files"? Maybe, maybe not. There are certainly some differences.

A 64-bit machine may spend 99.99% of its time executing 64-bit machine code once booted; but during the initial seconds it may have to execute some 32-bit machine code.

Likewise, a fully-loaded OS will execute in privileged mode and the rest of the code execute in user mode. But during bootstrapping most of the code may execute in privileged mode - or rather, in some "simply unprotected" mode, because the CPU mechanism for software fault handling may not have been fully initialized.

Code that needs to execute without the OS, obviously cannot make OS calls. They can still make jumps and subroutine calls to other code - as long as they are located within the same piece of code that is loaded into RAM in one swoop.

This brings up the "size limitation" of bootstrapper code. The previous stage has to know exactly how big is the code size of the next stage. That amount of executable code/data would be brought into RAM before any of it can be executed. In the absence of an OS (and also of any memory-management mechanism), the bootstrapper cannot make subroutine calls located outside what has been brought into RAM - unless if the bootstrapper knows how to load that the extra code.

The BIOS may have to provide a way to facilitate (simplify) the loading of extra data from the storage disk. Performance or security is not the concern - the only concern is simplicity for the caller (which is the bootstrapper). Otherwise, that would be a very tedious task, and would eat up the precious space the bootstrapper code has to fit in.

What formats are used for such bootstrapping code?

These code must follow some kind of conventions in order to work correctly. Whether these conventions qualify as "a format" is a word-play.

For example, the starting offset of the first machine instruction in the bootstrapping code must be specified. Otherwise, how else do you start executing it?

Some bootstrapping code are required to carry a checksum, or even a digital signature (i.e. become digitally signed), to prevent trying to execute a bootstrapper whose data is corrupted, or spoofed or tampered with by malicious intent.

These conventions must be agreed upon by the machine manufacturers, operating systems vendors and/or maintainers, and so on.


问:
Different license for logo files
I'm working on software that I intend to release under the terms of the GPL 3. However, I'd like to exempt the name and logo: the images with the logo should only be used with official releases, and only the official releases should be allowed to use the original project name. Forks should use a different name and logo to avoid confusion.

How do I specify this license modification in my project's documentation?

答:
You run the issue of having un-intended consequences if you dis-allow the logo and name from being used in "non-official releases"

For example, if lets say debian was to branch your project to include in their distro (without modification), or I choose to provide a compiled binary version which is compatible with raspberry pi. In both of those cases your project might not have any modification. Would these be acceptable options for you ?

A "Sly" way of protecting your logo and name would be to trademark them and then have a additional licence for their acceptable use (but be aware that in the event that if your trademark is infringed in some manner then you MUST defend it in court otherwise it can be considered lost)

Title: Different license for logo files


答:
Back in the stone age of computing, one of the common modes of booting up was to
read an executable program into memory completely under hardware control and then
start running it.

The PDP-10 for example, could command the paper tape reader to read
a block of data, take the data presented and stuff it into memory, and
then start running it when the block was complete.  This was used to
read a 16 instruction program which was enough to read more data from
the tape and place it in controlled locations of memory, and eventually
to start the bigger program which could run the console tty, read the
hard disk, and load the operating system.

Title: Do bare computer systems (without OS installed) use (executable) files?

Body:
As far as I read, files are introduced in OS books. Before an OS is installed on a bare computer system, does the computer use files?

In particular, executable files have formats in OSes, e.g. executable files have ELF format in Linux, which can guide the loader in the OS to load them into memory when running them. Before installation of an OS, does the computer system have the concept of executable files or something similar for storing programs?

If so, what is their format, for example, on a X86 or X86-64 bit bare computer machine?

Thanks.

I am not asking about booting but I am curious how a program is stored on a bare computer. A program may be for booting or not for booting. In particular, I am interested in how a user program is stored on a bare computer.


问:
best way to export binary data with additional text attributes to a stream
I would like to create a command line API in a Java application to export a binary blob to stdout. I would additionally like to export certain attributes about the blob, ideally in a non-binary format. The goal is to output this data in a manner that is convenient and efficient to write and read. I am fairly set on using stdout because it allows me to easily pipe the data into another process without creating intermediate files, which is a huge convenience.

I could write the text attributes on one tab-separated line and follow them by the binary blob. But since stdout is not structured, it would be awkward to parse if text and binary data are mixed. For example, the stream would probably have to be read in binary mode until a byte equalling an ASCII newline character is found and then the data would have to be split at that point.

Alternately I could wrap all the data in a structured format. The formats that I am most familiar with, like JSON and XML, are text formats and thus the binary data would have to be encoded, which would greatly increase computation time and data size. But there may be formats designed for this purpose.

Thirdly, I could implement a binary format similar to common file formats with a header containing fields that either have fixed byte length or are preceded by byte lengths. However, I am concerned that such a format would be unnecessarily non-standard and annoying to write and parse. In particular, I don't see the benefit of such a format over the first option where a newline separates the attributes and data.

There may be other options as well but I'm not thinking of any good ones. I would very much appreciate others' suggestions on this matter.

答:
If you just need a simple solution, and you can tolerate non-ASCII bytes in the header region, just use Protocol Buffers.

Link to Protocol Buffers

It is safe to use JSON for the human readable header of your file, followed by the raw binary blob without encoding or encapsulation, with the following preconditions:

Link to JSON specification

Your JSON needs to be an object at the top level.

This means your entire human readable header will be delimited by an opening brace, and a closing brace.

Anything else in between are properly quoted, escaped, and balanced.

You need to be specific about newlines.

Newlines that occur inside the JSON stream can be handled liberally.

However, you must be strict about whether a newline (or any other characters or byte sequences) are allowed to occur between

The end of the JSON stream, and

The beginning of the binary blob.

Remember that newline have different representations on different OSes.

Also, be explicit about the handling of consecutive occurrences of newlines. That could result from common programming mistakes which leave you with no choice but to tolerate and work around it.

You first stage of parsing needs to be done a JSON reader that detects the end of the top-level object, and ignores the rest of unencapsulated binary data, as explained above.

This first-stage parser do not need to handle the metadata; it just need to correctly identify the end of the header.

Once the header is separated, it can be passed into a second JSON reader which loads the metadata into objects.

If you are concerned about the need for software to extract the binary blob without having to rely on a correctly implemented JSON seeker, you may try this simple hack:

Make the requirement that the first field value of the top-level JSON object is a decimal number that is the number of bytes of the binary blob.

Your non-JSON-aware reader can then quickly delimit the binary blob as follows:

Open the stream in binary mode.

Discard all bytes not in the ASCII range of decimal digits, '0' - '9', until the first decimal digit is found.

Parse the decimal digit until a non-digit is found.

Seek to the end of file, and then recalculate the starting offset of the binary blob by subtracting its expected length (detected above) from its end position.

If you need the whole transmission to be sequentially parseable (streamable), you can do this instead:

Encode the metadata in JSON in a memory stream.

Do not write it to the output yet; that will be several steps later.

Be specific about the output encoding.

From the next step and on, we will treat it as a byte stream, which means it cannot be "edited" after this step.

Get the number of bytes of the encoded JSON byte stream.

Transmit this byte count as ASCII decimal-encoded number, followed by the newline.

As mentioned above, be explicit about what "newline" means.

Transmit the encoded JSON byte stream (from the memory stream), exactly as it is.

The number of bytes transmitted must match the ASCII decimal-encoded number.

Transmit the rest of the binary blob.

As a slight modification, you can probably transmit the byte stream lengths of both the JSON stream and binary blob.


答:
Since you're not talking about booting, your answer is actually that the concept of "executable," or even "files" is rather irrelevant.

The concept of files is an OS concept.  Without an OS, all you have is a harddrive, with some bits on it.  It is the OS that gives structure to that information that makes it meaningful to think of the data as a file.

For a "bare" computer, without considering booting, the idea of "storing user programs" is meaningless besides the very boring definition of "it stores the files by putting the 1's and 0's on a harddrive."  At this level, these 1's and 0's are indistinguishable from those of text, or images, or anything else because there is no "defined" structure.

People are focusing on booting because that is where your concept of "executable file" becomes meaningful for the first time.  When a BIOS boots (from ROM), one of its last tasks is identifying a media to boot from (i.e. a hard drive), and "executing" something from it.  This is usually implemented as "the bios will command the harddrive to produce the 1's and 0's from a specific numbered location on the harddrive.  These 1's and 0's will then be stored in memory, and the Instruction Pointer of the 1st CPU will be pointed at those 1's and 0's."

This is the point where we get closest to an answer to your question.  This block of 1's and 0's is formatted in a way that is defined by the CPU as a set of instructions.  I can't quite call it a file, but is definitely a continuous block of CPU defined values loaded from a harddrive.

Now this particular set of instructions gets to take ownership of the computer.  It will command everything from here on out.  If I wished, I can now go ask the harddrive for a different block of 1's and 0's, store those in memory, and "run them."  This suggests that this block of 1's and 0's known as "machine code" would be an answer to your question "how are user programs stored."  However, it is an incomplete answer.  I could also write my block to go read from the harddrive, then invert every bit it read, before jumping to that data as a set of instructions.  In this case, now the 1's and 0's are not "machine code," but rather a sort of encoded machine code.  This shows that there is no one "defined" way to store user programs on a bare computer except for the first program, which is special.

Now eventually we're going to run some programs that bring in the concept of a file system on the harddrive.  Now, for the first time, we have a concept of a file, so we can talk about "executable files."  However, because we're so far along in the process, there is no one way they get stored.  As shown before, we could arbitrarily choose to invert every bit.

So the reason why your question involves terms that don't really go together is that the concept of an "executable file" is at odds with the idea of a "bare computer."  The two words simply do not go together.  However, in the initial moments of booting, there is a section of the harddrive, which is not a file but gets really close to being called a file, which is in an executable format defined by the CPU.


答:
Files are a low-level abstraction provided by the operating system thru some file system layer. Another important abstraction provided by OSes is processes (running instances of programs). The OSdev site has interesting practical information. The underlying bar metal computer (e.g. your x86 laptop or desktop) does not know about files.... It is reading and writing sectors (often blocks of 512 bytes or of 4096 bytes) on disks (and the OS builds the file abstraction above that). Your usual OS (Linux or Windows) is using the file abstractions to store programs. But the bar metal computer is just executing machine code instructions (and some of them are read from the disk by the OS). At the lowest level, close to the hardware, programs do not really exist (only machine code)! Executables (hence programs) and processes are also an abstraction (& convention) provided and handled by the OS. On Linux, most executable binaries are in ELF.

But you could imagine an operating system without any files. You'll have to write such an OS from scratch, running on the bare metal (and of course you'll have to define some notion of program, care about how that thing boots, run programs and uses the disk). It could have some orthogonal persistence model (like Phantom, EROS, etc...)

In the 1980s & 1990s some Lisp machines did not have any files. They persisted their entire state on the disk.

In practice computers are becoming increasing complex. You can look at UEFI and at the Grub boot loader as having some limited form of files. and some firmware (like Open Firmware) also provide a limited form of files.

Another amusing way of looking at this is to imagine that aliens might have computers which do not use any files (but something else). Files are an invention (somehow related to technology and social issues of the IT sector in the 1960s)

And of course some small microcontrollers don't have file systems. My washing machine probably has some 8 bit microcontroller, but no file system.

I guess that files are becoming less relevant than before (databases being increasingly important). Notice that a plain Unix-like filesystem might not be the best way to organize your data on some multi terabyte disk. You probably want to store more meta-data about it than a native filesystem offers (and you might use some database for that).


问:
How to save many changes to database data?
I'm working on a feature which will pull many (say, 1000-5000) rows from a database, display them to the user and allow the user to edit them.  This editing may involve changing text; adding rows at the beginning, middle or end of the dataset; and/or deleting rows.  The order of the rows is important (i.e., I can't just shift a newly-added row to the end of the dataset.)

At any point in the editing, the user can hit a save button, at which point the changes are recorded in the database.

Here's where my question comes in: is there an accepted pattern for how to do this type of thing?  Thus far, I've just been deleting all the originally-pulled rows and then reinserting the newly-saved rows.  However, as each row has an auto-incremented ID, I'm starting to get worried (you can see how a single user could easily blow through 100,000 IDs in no time at all).  At some point in the future, I may also have foreign keys which depend on these rows IDs and of course this method will wreak havoc on them.

On the other hand, modifying each individual changed row--including keeping track of deletions and additions--seems like a recipe for mistakes.

答: A technique I've used to modify and reorder an arbitrary number of records is to merge/upsert the rows, retaining the auto-incremented IDs and using a separate column to manage sorting. The sort order is tracked by the front-end application and passed as an additional query parameter when saving the records, allowing new records to be placed in any position by the application. For MySQL, use the INSERT INTO... ON DUPLICATE KEY UPDATE syntax.

OwnerDisplayName: Swiftheart


问:
How do I find out what type of exception I am supposed to raise?
I suppose this question is valid for any programming language that can handle (or at least throw) an exception. However I will stick to Python as an example.

The top 2 answers to the following question disagree with each other on a particular point.
https://stackoverflow.com/questions/2052390/manually-raising-throwing-an-exception-in-python

At this moment (2015 March 14 Sat 2354 hrs) it seems that there's a growing consensus around the second answer (Aaron Hall's answer in case any of this changes in the future). And I think I do get the point about being specific about the type of exception I am supposed to raise. A hierarchy for Python is given here: https://docs.python.org/3/library/exceptions.html#exception-hierarchy

Now, I am at point where I want to manually raise an exception when a division results in a non-integer. Specifically, I have a 2D array and I also have the number of columns in it. If the division of the former by the latter results in an non-integer, it means that the number of rows is a non-integer, and thus something's messed up somewhere. And I want to raise an exception.

Why would it be wrong to just include raise Exception("Something's wrong. Number of rows is not an integer!") in my code? The categories in the hierarchy are just words in English, but I am not able to choose the best category for my purpose. So what's wrong in clearly explaining the issue in my message (which for the present example is the problem that the number of rows is not an integer)?

答:
Raising a generic xception and differentiating it just by its message would be wrong because then, if you have many of them and want to react appropriately, how would you distinguish them?

Regarding the choice of the exception, taking your example, I would say that ArithmeticError is something pretty low-level and focused on the arithmetic aspects of the problem. In your case, is it an arithmetic error the fact that 7 is not divisible by 3? No, arithmetically it's correct.

That's a problem if taken from another point of view, namely the one of your application logic, so such exception would make sense only in your application. I would make my own one (e.g. NonDivisibleTableError derived from Exception).

Now, how could that happen? That's another issue, but a quick search showed that also in Python it's possible to specify a cause when throwing an exception (see raise/from). This way you can describe what went wrong at the different levels of your application, (e.g. NonDivisibleTableError caused by some IOError), and give the user a more reasoned error message.


问:
Is it wise for a high level developer to spend time studying assembly?
It is clear that the knowledge of low level stuff is very important in our work.

But in a situation where you're already developing commercial software on a high level, and when you already have a chosen direction but don't have any assembly skill, isn't it more reasonable to focus on studying stuff related to your direction? Or is there a reason you should spend some time to learn the low-level basics anyway?

When is it too late, and when it is not? And if it is not too late, then how would one go about learning optimally (in the sense of not spending excessive time to get some depth and understanding)?

答:
It had been very important in my prior life as a supercompuer guru. Back then
I felt you didn't understand a machine until you had written at least several hundred lines of assembler, and tinkered with it trying to squeeze out performance. As very few programmers wanted to go that deep, it made me really indispensable. And I still have a common language when talking with HW designer types.

But, really the need/benefit for this is mostly a couple of decades past. Between compiler advances, and advanced out of order execution HW there is very little scope for being able to play the hero by writing assembler any more. Although I think it useful to understanding how things work. I plan on teaching my kids (freshmen CS majors) to program in a very simplified assembler on a simple virtual machine, just so they have a feel for what goes on. Hopefully we can play with stuff like unrolling, software pipelining, caches, and prefetching, bottom loading etc. So at least they will know that at some level this stuff is going on.


答:
Before an OS is installed on a bare computer system, does the computer use files?

No.  At startup some code is copied from an EPROM into memory at a known location and the processor executes those instructions.  All it does is load execute instruction at the 'current' memory address increment it and repeat forever.  The CPU is unaware that a harddisk controller or anything else is even connected let alone do anything useful with any of it - it requires instructions on how to do that and those instructions are usually the lowest layer of an operating system.

does the computer system have the concept of executable files or something similar for storing programs?

With nothing to put files on there is no file system and no file format.  Initially everything is loaded from an EPROM into RAM (main memory) and then executed instruction by instruction.  So far as the CPU is concerned they're just an array of bytes.

The BIOS is an example of code that the EPROM contains - it is the code for a (very simple) operating system which does what it needs to (like wake up disk controllers and other peripherals) and look for a another piece of code to run.  The same mechanism that boots your system and allows it to operate enough for you to load/install your OS of choice is the one that kickstarts everything time you power up the system.

If you felt that inclined and had the right information about the exact hardware on your motherboard you can write your own EPROM and run code from that.  Of course at some point you'd need to reuse functions and as that need increases you'd find yourself writing your own OS and all the headaches that go with it...


答:
You are creating a user interface -- code is a user interface, where the "user" is another programmer, or another function. If you were the user of your code rather than the developer, what would make your code easier to use? So, look at this problem from the perspective of someone calling your function. What would be the most useful exception you could give? Note: there may be more than one answer, in which case it really doesn't matter too much. The point is, make your code as easy to use as possible.

The other important thing to remember is this: you may be only sending one exception, but your code as a whole could be sending many. The exception you throw needs to play nicely with all of the other possible exceptions (meaning: it must be distinguishable from the other exceptions).

In this specific case (and in most cases...), a generic exception isn't particularly useful. There could be more than one way that your function fails. Maybe the inputs are floats instead of integers. Maybe they are strings. Or maybe the inputs result in a divide by zero. The caller may care about these distinctions. Maybe they won't, but they might. And if not now, they might in the future.

Title: How do I find out what type of exception I am supposed to raise?

Body:
I suppose this question is valid for any programming language that can handle (or at least throw) an exception. However I will stick to Python as an example.

The top 2 answers to the following question disagree with each other on a particular point.
https://stackoverflow.com/questions/2052390/manually-raising-throwing-an-exception-in-python

At this moment (2015 March 14 Sat 2354 hrs) it seems that there's a growing consensus around the second answer (Aaron Hall's answer in case any of this changes in the future). And I think I do get the point about being specific about the type of exception I am supposed to raise. A hierarchy for Python is given here: https://docs.python.org/3/library/exceptions.html#exception-hierarchy

Now, I am at point where I want to manually raise an exception when a division results in a non-integer. Specifically, I have a 2D array and I also have the number of columns in it. If the division of the former by the latter results in an non-integer, it means that the number of rows is a non-integer, and thus something's messed up somewhere. And I want to raise an exception.

Why would it be wrong to just include raise Exception("Something's wrong. Number of rows is not an integer!") in my code? The categories in the hierarchy are just words in English, but I am not able to choose the best category for my purpose. So what's wrong in clearly explaining the issue in my message (which for the present example is the problem that the number of rows is not an integer)?


问:
why is the latter function 10% faster although it must create the variables over and over again?
```<code>var toSizeString = (function() {

 var KB = 1024.0,
     MB = 1024 * KB,
     GB = 1024 * MB;

  return function(size) {
    var gbSize = size / GB,
        gbMod  = size % GB,
        mbSize = gbMod / MB,
        mbMod  = gbMod % MB,
        kbSize = mbMod / KB;

    if (Math.floor(gbSize)) {
      return gbSize.toFixed(1) + 'GB';
    } else if (Math.floor(mbSize)) {
      return mbSize.toFixed(1) + 'MB';
    } else if (Math.floor(kbSize)) {
      return kbSize.toFixed(1) + 'KB';
    } else {
      return size + 'B';
    }
  };
})();
</code>```

And the faster function:(note that it must always compute the same variables kb/mb/gb over and over again). Where does it gain performance?

```<code>function toSizeString (size) {

 var KB = 1024.0,
     MB = 1024 * KB,
     GB = 1024 * MB;

 var gbSize = size / GB,
     gbMod  = size % GB,
     mbSize = gbMod / MB,
     mbMod  = gbMod % MB,
     kbSize = mbMod / KB;

 if (Math.floor(gbSize)) {
      return gbSize.toFixed(1) + 'GB';
 } else if (Math.floor(mbSize)) {
      return mbSize.toFixed(1) + 'MB';
 } else if (Math.floor(kbSize)) {
      return kbSize.toFixed(1) + 'KB';
 } else {
      return size + 'B';
 }
};
</code>```

答:
Modern JavaScript engines all do just-in-time compilation.  You can't make any presumptions about what it "must create over and over again."  That sort of calculation is relatively easy to optimize out, in either case.

On the other hand, closing over constant variables is not a typical case you would target JIT compilation for.  You typically create a closure when you want to be able to change those variables on different invocations.  You're also creating an additional pointer dereference to access those variables, like the difference between accessing a member variable and a local int in OOP.

This sort of situation is why people throw out the "premature optimization" line.  The easy optimizations are already done by the compiler.


答:
One example involves a closure, the other does not. Implementing closures is kinda tricky, since closed over variables do not work like normal variables. This is more obvious in a low-level language like C, but I'll use JavaScript to illustrate this.

A closure does not only consist of a function, but also of all variables it closed over. When we want to invoke that function, we also need to provide all closed over variables. We can model a closure by a function that receives an object as first argument that represents these closed over variables:

```<code>function add(vars, y) {
  vars.x += y;
}

function getSum(vars) {
  return vars.x;
}

function makeAdder(x) {
  return { x: x, add: add, getSum: getSum };
}

var adder = makeAdder(40);
adder.add(adder, 2);
console.log(adder.getSum(adder));  //=> 42
</code>```

Note the awkward calling convention closure.apply(closure, ...realArgs) this requires

JavaScript's builtin object support makes it possible to omit the explicit vars argument, and lets us use this instead:

```<code>function add(y) {
  this.x += y;
}

function getSum() {
  return this.x;
}

function makeAdder(x) {
  return { x: x, add: add, getSum: getSum };
}

var adder = makeAdder(40);
adder.add(2);
console.log(adder.getSum());  //=> 42
</code>```

Those examples are equivalent to this code actually using closures:

```<code>function makeAdder(x) {
  return {
    add: function (y) { x += y },
    getSum: function () { return x },
  };
}

var adder = makeAdder(40);
adder.add(2);
console.log(adder.getSum());  //=> 42
</code>```

In this last example, the object is only used to group the two returned function; the this binding is irrelevant. All the details of making closures possible – passing in hidden data to the actual function, changing all accesses to closure variables to lookups in that hidden data – are taken care of by the language.

But calling closures involves the overhead of passing in that extra data, and running a closure involves the overhead of lookups in that extra data – made worse by bad cache locality and usually a pointer dereference when compared with ordinary variables – so that it's not surprising that a solution that does not rely on closures performs better. Especially since everything your closure saves you to do is a few extremely cheap arithmetic operations, which might even be constant-folded during parsing.

Title: why is the latter function 10% faster although it must create the variables over and over again?

Body:
```<code>var toSizeString = (function() {

 var KB = 1024.0,
     MB = 1024 * KB,
     GB = 1024 * MB;

  return function(size) {
    var gbSize = size / GB,
        gbMod  = size % GB,
        mbSize = gbMod / MB,
        mbMod  = gbMod % MB,
        kbSize = mbMod / KB;

    if (Math.floor(gbSize)) {
      return gbSize.toFixed(1) + 'GB';
    } else if (Math.floor(mbSize)) {
      return mbSize.toFixed(1) + 'MB';
    } else if (Math.floor(kbSize)) {
      return kbSize.toFixed(1) + 'KB';
    } else {
      return size + 'B';
    }
  };
})();
</code>```

And the faster function:(note that it must always compute the same variables kb/mb/gb over and over again). Where does it gain performance?

```<code>function toSizeString (size) {

 var KB = 1024.0,
     MB = 1024 * KB,
     GB = 1024 * MB;

 var gbSize = size / GB,
     gbMod  = size % GB,
     mbSize = gbMod / MB,
     mbMod  = gbMod % MB,
     kbSize = mbMod / KB;

 if (Math.floor(gbSize)) {
      return gbSize.toFixed(1) + 'GB';
 } else if (Math.floor(mbSize)) {
      return mbSize.toFixed(1) + 'MB';
 } else if (Math.floor(kbSize)) {
      return kbSize.toFixed(1) + 'KB';
 } else {
      return size + 'B';
 }
};
</code>```

Body:
One example involves a closure, the other does not. Implementing closures is kinda tricky, since closed over variables do not work like normal variables. This is more obvious in a low-level language like C, but I'll use JavaScript to illustrate this.

A closure does not only consist of a function, but also of all variables it closed over. When we want to invoke that function, we also need to provide all closed over variables. We can model a closure by a function that receives an object as first argument that represents these closed over variables:

function add(vars, y) {
  vars.x += y;
}

function getSum(vars) {
  return vars.x;
}

function makeAdder(x) {
  return { x: x, add: add, getSum: getSum };
}

var adder = makeAdder(40);
adder.add(adder, 2);
console.log(adder.getSum(adder));  //=> 42

Note the awkward calling convention closure.apply(closure, ...realArgs) this requires

JavaScript's builtin object support makes it possible to omit the explicit vars argument, and lets us use this instead:

function add(y) {
  this.x += y;
}

function getSum() {
  return this.x;
}

function makeAdder(x) {
  return { x: x, add: add, getSum: getSum };
}

var adder = makeAdder(40);
adder.add(2);
console.log(adder.getSum());  //=> 42

Those examples are equivalent to this code actually using closures:

function makeAdder(x) {
  return {
    add: function (y) { x += y },
    getSum: function () { return x },
  };
}

var adder = makeAdder(40);
adder.add(2);
console.log(adder.getSum());  //=> 42

In this last example, the object is only used to group the two returned function; the this binding is irrelevant. All the details of making closures possible – passing in hidden data to the actual function, changing all accesses to closure variables to lookups in that hidden data – are taken care of by the language.

But calling closures involves the overhead of passing in that extra data, and running a closure involves the overhead of lookups in that extra data – made worse by bad cache locality and usually a pointer dereference when compared with ordinary variables – so that it's not surprising that a solution that does not rely on closures performs better. Especially since everything your closure saves you to do is a few extremely cheap arithmetic operations, which might even be constant-folded during parsing.


问:
Licensing code submitted after job interview
I applied for a job in a small company (~25 employees) on December and after a month the CEO of the company wrote to me that he is interested to interview me. During the interview I got a bad impression of the employer and decided that I would not want to work for the company. However, the interviewer asked me whether I want to do a mini-project for them involving a complex but very interesting scientific problem. I told them I didn't mind, because I am interested anyway in this kind of work.

It took me 3days to a week to finish it. My technique would easily become much faster with a few more modifications, but I was not ready to invest more time and end up having my code stolen or used and getting the job denied. I am going to write a short description of the technicalities from which someone who is smart enough can see the extension to the technique I used to make it much faster.

I was thinking of licensing my code under MIT License and the documentations under something like creative commons. This will theoretically/psychologically gaurantee me that they won't steal the code (though they can steal it if they want and I wouldn't know). I am explaining in my documentation how the code could thereotically be improved in specific places and this will give them a gist of my abilities.

My question to the forum is: Am I being rude or "illegal" by trying to license the code and my text?

The problem was given to me as a pdf file and on the file it was written "for internal use only", I didn't sign any contract or made any promises. I feel this is the best way I can protect myself and I still want to solve the problem because of my interest in it and because this is the kind of work I want. Worst case is that I don't get the job but after this work I can almost publish a paper on this problem and at least improve my scientific profile.

Edit : Just to let you guys know. I decided to license my work and send it to them. For future applicants who have my situations, I will give an update of what happened.

答:
There's a couple of different aspects here that need to be evaluated.

In the absence of a contract between you and the potential employer, you continue to own the copyright for any code you write in consideration of being hired.  Likewise, unless you explicitly state a license on the code when you provide it to the potential employer, then you have not licensed the code to them.

Since you own the copyright to the code, you can do whatever you want with it later on.  That also includes releasing the code under whatever license you like such as the MIT, BSD, Creative Commons, or GPL licenses.

As you haven't licensed the code to the potential employer, they should not use your code in any of their applications.  Why not?  Because you haven't given them permission to do so (yet).  Note that if you later release the code under a permissive license (such as MIT or BSD) then they would have license to use your code.  You could put a poison-pill on your code by licensing it with the GPL which could potentially force their application to be re-licensed as GPL if they used your code and weren't careful in how they incorporated it.

Unfortunately, copyright law and employment law varies (sometimes considerably so) by jurisdiction, and if you're really worried about this aspect then you'll need to consult an attorney specializing in intellectual property.

You also asked:

Am I being rude or "illegal" by trying to license the code and my text?

No, actually it's quite the contrary.  By licensing the submitted code, you're provided explicit permission to use (or not) the code that you provided.

The potential employer has made two significant mistakes here.

The first mistake involves disclosure.  They didn't have you sign any documentation or non-disclosure agreements prior to providing the assignment to you.  If that assignment is part of their mainline work, then the risk of exposure is on them, not you.  Just because you interviewed with them, you are not bound by any legal requirements regarding non-disclosure even though you may feel ethically bound to not disclose.

The second mistake involves licensing.  Giving you an assignment related to their mainline of work without documentation or a contract makes things very problematic for them.  As you haven't provided the code under a license to them, they are not allowed to use your code.  Lack of a contract leaves things in a questionable state, which puts a legal burden (aka headache) on them if they want to use your code.  The worst case is they have to come back to you and say "Hey, we don't want to hire you but we still want to use your code.  Will you license it to us?"

The above is one of the reasons why most companies do not have interview candidates develop code against problems the company is actually experiencing with their applications.  It's far easier to come up with a smaller design project unrelated to their applications in order to evaluate your code writing ability.  It creates intentionally throw-away code that has no legal bearing upon the company's mainline activities.


问:
Use interface or abstract class?
Now the title might seem like the question has been asked before but let me explain my situation and you'll see why I am asking this question.

Let's consider this interface :

```<code>public interface IListChangedListener {
    public event EventHandler ItemAdded;
    public event EventHandler ItemRemoved;
}
</code>```

If someone wants to implement this interface, they would have to check if ItemAdded is null and only if it is not null, they would call it. Well, I want to simplify their job by giving an in built function which will do the same. Just calling that function will check if the corresponding event is null, and if it isn't, it'll fire its corresponding event.

The problem is, this is an interface. So I can't define a method. So I thought I might go with an abstract class. But considering the situation, it would be best suited to make this as an interface rather than an abstract class.

So do I just drop the idea of giving an in built function? Or do I make it an abstract class? Which better suits the situation? I am having a tough time deciding which one to use. Some help please?

答:
As usual:

If you need to implement some methods, the interface is not a solution. You have to use an abstract class.

On the other hand, if you need to describe the behavior, especially in a context where classes which have this behavior might already have a parent class, you have to use an interface, since in C#, a class cannot have multiple parents.

If you need the benefits of both worlds, don't use neither an interface, nor an abstract class, but have a separate object used within the objects.

In your case, you need to describe the behavior. The business logic brought by an eventual abstract class or a dedicated class is not that useful: it's just a null check, nothing more. Therefore, the repetition of those null checks in different classes which implement the interface wouldn't be a serious violation of DRY principle.

Agreed, most implementers will end up creating two methods which check for nullity and raise the event, but again, this is not that complicated to do (nor would the logic change over time).

From the comments, it appears that you are reinventing the wheel. In .NET Framework, there is already a class which does what you need: ObservableCollection<T>.

It has nothing to do with WPF: it is a part of System.Collections.ObjectModel namespace, the one which contains many things related to collections, including Collection<T> itself, ReadOnlyCollection<T>, etc. You can use those collections outside WPF, that is in a console application, a Windows Forms project or a website.

Title: Use interface or abstract class?


问:
Most MVC-strict php framework
I have been trying to wrap my head around MVC pattern for about 6 months.I've read tons of articles, Q&A, and blog posts about MVC and HMVC patterns, but I just simply don't get it 100%.

I tried learning MVC by exercising one of widely used PHP MVC framework, CodeIgniter. I've implemented few internal websites for my company with it. And STILL, I don't 100% get it. I believe one of the best ways to learn something is to follow strictly defined rules.

So my question is: What is the most strict PHP framework in terms of how MVC pattern is implemented? One that defines how I use models, controllers, and views so that I can completely get what MVC is?

答:
I understand this post is year old, which is ironically the reason I am posting this response. First off, some of the people who answered this question are right. You're never really going to find a PHP Framework that come "MVC Ready" right out of the box...necessarily. Seeing as the framework is supposed to be a foundation where Dev's can build upon it, following MVC. However, in the last year since this has been posted, some of the PHP frameworks out there have sure come a long way.

I messed around with CakePHP for a bit, even to this day it is a horrible, messy setup of directories and structure, there is no clear distinction between logic, it has quite poorly commented code, and everything is kind of crammed together in one bundled mess. That is not a rant on CakePHP mind you, that is simple truth.

Zend, is excellent. They provide excellent documentation & code commenting, have a very friendly community, and provide a very nice framework for developers that are novice, and intermediate alike. They have come a long way since the OP posted this.

And to the people saying that there is no such framework to answer the OP's question, they are right as I said above. However, they are also wrong as well. Zend, Laravel and CodeIgniter are amazing frameworks, and while they don't "give" you MVC, they definitely pave a roadway for you as a developer to create a beautifully built, MVC applications, considering that you, as the developer follow good MVC practices.

To those in this thread saying CodeIgniter is horrible. You are quite wrong, at least by today's standards. At the time of this post I wasn't into frameworks so I hadn't looked at it then. Therefor at that time it might have been horrible. But I use it ALL of my web applications now. They do a great job of creating a solid framework with an understandable directory structure, as well as give you some amazing tools to start MVC'ing away. They do a great job at logic distinction, they have an awesome community for support, and they overall provide a great, free framework which, again if you follow good MVC practices, can turn into some amazing applications.

To the main point. I wanted to interject my opinion on this subject. You'll never find that perfect, MVC built, out-of-the-box framework. However, if you utilize good MVC practices, and choose a solid framework such as Zend, Laravel and/or CodeIgniter you'll be fine. Because the raw truth is, that the MVC is up to the developer how s/he implements good practice and not the framework. The framework offers the foundation, the rest is up to the developer.

Good Frameworks to use as references

CodeIgniter

Zend Framework

Laravel

Symfony 2 (Added after reading comment, because it is also an excellent framework)

Just remember when using these, it is up to you as the developer to follow the good MVC practices. There are tons and tons of tutorials out there on good MVC practices. I stumbled upon a gentleman's website that has some amazing guidelines, and he aims towards proper MVC, and so far his blog posts have been pretty dang good, and he is a great place to start learning.

Reference

Tom Butler's Programming Blog: https://r.je/

Title: Most MVC-strict php framework


答:
Variables are cheap. Execution contexts and scope chains are expensive.

There are various answers that essentially boil down to "because closures", and those are essentially true, but the problem isn't specifically with the closure, it's the fact that you have a function referencing variables in a different scope. You'd have the same problem if these were global variables on the window object, as opposed to local variables inside the IIFE. Try it and see.

So in your first function, when the engine sees this statement:

```<code>var gbSize = size / GB;
</code>```

It has to take the following steps:

Search for a variable size in the current scope. (Found it.)

Search for a variable GB in the current scope. (Not found.)

Search for a variable GB in the parent scope. (Found it.)

Do the calculation and assign to gbSize.

Step 3 is considerably more expensive than just allocating a variable. Moreover, you do this five times, including twice for both GB and MB. I suspect that if you aliased these at the beginning of the function (e.g. var gb = GB) and referenced the alias instead, it would actually produce a small speedup, although it's also possible that some JS engines already perform this optimization. And of course, the most effective way to speed up execution is simply not to traverse the scope chain at all.

Keep in mind that JavaScript is not like a compiled, statically-typed language where the compiler resolves these variable addresses at compile time. The JS engine has to resolve them by name, and these lookups happen at runtime, every time. So you want to avoid them when possible.

Variable assignment is extremely cheap in JavaScript. It might actually be the cheapest operation, although I have nothing to back up that statement. Nonetheless, it's safe to say that it's almost never a good idea to try to avoid creating variables; almost any optimization you try to do in that area is actually going to end up making things worse, performance-wise.

Body:
Variables are cheap. Execution contexts and scope chains are expensive.

There are various answers that essentially boil down to "because closures", and those are essentially true, but the problem isn't specifically with the closure, it's the fact that you have a function referencing variables in a different scope. You'd have the same problem if these were global variables on the window object, as opposed to local variables inside the IIFE. Try it and see.

So in your first function, when the engine sees this statement:

var gbSize = size / GB;

It has to take the following steps:

Search for a variable size in the current scope. (Found it.)

Search for a variable GB in the current scope. (Not found.)

Search for a variable GB in the parent scope. (Found it.)

Do the calculation and assign to gbSize.

Step 3 is considerably more expensive than just allocating a variable. Moreover, you do this five times, including twice for both GB and MB. I suspect that if you aliased these at the beginning of the function (e.g. var gb = GB) and referenced the alias instead, it would actually produce a small speedup, although it's also possible that some JS engines already perform this optimization. And of course, the most effective way to speed up execution is simply not to traverse the scope chain at all.

Keep in mind that JavaScript is not like a compiled, statically-typed language where the compiler resolves these variable addresses at compile time. The JS engine has to resolve them by name, and these lookups happen at runtime, every time. So you want to avoid them when possible.

Variable assignment is extremely cheap in JavaScript. It might actually be the cheapest operation, although I have nothing to back up that statement. Nonetheless, it's safe to say that it's almost never a good idea to try to avoid creating variables; almost any optimization you try to do in that area is actually going to end up making things worse, performance-wise.