问:
Looking for a DP algorithm for a specific packing problem
I have the following problem to solve:

Given a ferry with length d and a list of n cars conataining their length we must load the cars on the ferry in an order in which they appear in the list on 2 different lanes (each one having length d). Write a program that given length d and the list of cars outputs maximal number of cars that can be loaded on the ferry.

It's quite easy to do in O(2^cars) with backtracking - we load car on the left and try all the possibilities then, we save maximum and load car on the right and do the same saving max again.

But I have a feeling this can be reduced to polynomial time with dynamic programming. How to tell whether my gut feeling is true?

答:
A possible approach is the following.

I am going to make the following assumptions. Let me know if either of them is actually incorrect. As soon as we encounter a car that can be added in neither of the lanes, then we stop adding cars to the ferry (it is not allowed to skip a big car to add a smaller car that comes latter in the list). I am going to make the assumption that  the sum of the length of all cars is below 2d. If it is not the case, this can easily be enforced in a preprocessing step. I am also going to consider that d is an integer value, as well as all car sizes.

What we are now going to do is solve a 0/1 knapsack problem to find if a set of car can fit in both lanes.

Here the size of the knapsack is d (it is actually a lane), the size of the items are the size of the cars and the value associated with the items are the size of the cars (ie, we want to fill one lane as much as possible). To solve this 0/1 knapsack problem you can use the DP algorithm outlined on the following wikipedia webpage: http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem (I am just going to reproduce it here so that the answer stands even if the wikipedia page would disappear):

Let us call s1, the size of car 1, s2 the size of car2, and so on (we are going to consider that we have n cars).

Define m[i,s] to be the maximum value that can be attained with a total size used less than or equal to s using cars up to i (first i cars).

We can define m[i,s] recursively as follows:
m[i,s]=m[i-1,s] if si > s\, (the new car is longer than the current size limit)
m[i,s]=max(m[i-1,s],\,m[i-1,s-si]+si) if si less or equal than s.

The solution can then be found by calculating m[n,d].

let us call s, the sum of the length of the cars in the solution from the knapsack problem. If the sum of all the cars length - s is less or equal than d, then all the cars considered for solving the knapsack problems can fit in the ferry (one lane being all those selected to be part of the knapsack solution, the other lane being the rest). If the sum of the length of the rest of the cars is more than d, then all the cars cannot fit in the ferry. Remove the last car from the list of the cars, and solve again the knapsack problem. Do this until the sum of the length of the not selected cars is below d.

The complexity of the DP algorithm to solve the knapsack problem is O(nd) and it needs to be solved at most n times -> complexity O(n^2d)

Here is a sketch of the solution in python:

```<code>def solveKnapsack(cars, lengthOfLane):
  m = [[0] * (lengthOfLane+1)]
  for s in cars:
    m.append([])
    for j in range(lengthOfLane+1):
      if s <= j:
        m[-1].append(max(m[-2][j],m[-2][j-s]+s))
      else:
        m[-1].append(m[-2][j])
  return max(m[-1])

def solveTwoLanes(cars, lengthOfLane):
  maxOneLane = solveKnapsack(cars, lengthOfLane)
  if sum(cars) - maxOneLane <= lengthOfLane:
    return len(cars)
  else:
    return solveTwoLanes(cars[:-1], lengthOfLane)

def main():
  # small example that should output 2.
  print solveTwoLanes([3,3,3,1],5)

if  __name__ =='__main__':main()
</code>```

Body:
A possible approach is the following.

I am going to make the following assumptions. Let me know if either of them is actually incorrect. As soon as we encounter a car that can be added in neither of the lanes, then we stop adding cars to the ferry (it is not allowed to skip a big car to add a smaller car that comes latter in the list). I am going to make the assumption that  the sum of the length of all cars is below 2d. If it is not the case, this can easily be enforced in a preprocessing step. I am also going to consider that d is an integer value, as well as all car sizes.

What we are now going to do is solve a 0/1 knapsack problem to find if a set of car can fit in both lanes.

Here the size of the knapsack is d (it is actually a lane), the size of the items are the size of the cars and the value associated with the items are the size of the cars (ie, we want to fill one lane as much as possible). To solve this 0/1 knapsack problem you can use the DP algorithm outlined on the following wikipedia webpage: http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem (I am just going to reproduce it here so that the answer stands even if the wikipedia page would disappear):

Let us call s1, the size of car 1, s2 the size of car2, and so on (we are going to consider that we have n cars).

Define m[i,s] to be the maximum value that can be attained with a total size used less than or equal to s using cars up to i (first i cars).

We can define m[i,s] recursively as follows:
m[i,s]=m[i-1,s] if si > s\, (the new car is longer than the current size limit)
m[i,s]=max(m[i-1,s],\,m[i-1,s-si]+si) if si less or equal than s.

The solution can then be found by calculating m[n,d].

let us call s, the sum of the length of the cars in the solution from the knapsack problem. If the sum of all the cars length - s is less or equal than d, then all the cars considered for solving the knapsack problems can fit in the ferry (one lane being all those selected to be part of the knapsack solution, the other lane being the rest). If the sum of the length of the rest of the cars is more than d, then all the cars cannot fit in the ferry. Remove the last car from the list of the cars, and solve again the knapsack problem. Do this until the sum of the length of the not selected cars is below d.

The complexity of the DP algorithm to solve the knapsack problem is O(nd) and it needs to be solved at most n times -> complexity O(n^2d)

Here is a sketch of the solution in python:

def solveKnapsack(cars, lengthOfLane):
  m = [[0] * (lengthOfLane+1)]
  for s in cars:
    m.append([])
    for j in range(lengthOfLane+1):
      if s <= j:
        m[-1].append(max(m[-2][j],m[-2][j-s]+s))
      else:
        m[-1].append(m[-2][j])
  return max(m[-1])

def solveTwoLanes(cars, lengthOfLane):
  maxOneLane = solveKnapsack(cars, lengthOfLane)
  if sum(cars) - maxOneLane <= lengthOfLane:
    return len(cars)
  else:
    return solveTwoLanes(cars[:-1], lengthOfLane)

def main():
  # small example that should output 2.
  print solveTwoLanes([3,3,3,1],5)

if  __name__ =='__main__':main()


问:
Is the 'finally' portion of a 'try ... catch ... finally' construct even necessary?
Some languages (such as C++ and early versions of PHP) don't support the finally part of a try ... catch ... finally construct. Is finally ever necessary? Because the code in it always runs, why wouldn't/shouldn't I just place that code after a try ... catch block without a finally clause? Why use one? (I'm looking for a reason/motivation for using/not using finally, not a reason to do away with 'catch' or why it's legal to do so.)

答:
Some languages offer both constructors and destructors for their objects (e.g. C++ I believe). With these languages you can do most (arguably all) of what is usually done in finally in a destructor. As such - in those languages - a finally clause may be superfluous.

In a language without destructors (e.g. Java) it is difficult (maybe even impossible) to achieve correct cleanup without the finally clause. NB - In Java there is a finalise method but there is no guarantee it will ever be called.

ContentLicense: CC BY-SA 3.0


问:
If you take a year or two out from being a developer, is it really that hard to get back into it?
I've been working as a developer for about 3 years now (straight from uni), I'm wondering, if I take a year or two out would it be impossible to get back into the industry?

I didn't get the gap year thing out of my system after uni, and I'm thinking that I should probably do it before I hit 30 (24 now), my main concern is that if I leave the industry now, I might not get back into it at all and end up working some dead end job.

The way I see things is, that general concepts / design patterns etc remain similar over the years, and it is mostly coding syntax / actual implementation that evolves, so it shouldn't move on dramatically.

Also, women developers (yes there are some out there!) take years out to have kids and still carry on with their career afterwards, so it can't be impossible.

Ultimatum : Would taking a year or two out destroy the (small) career I've built up so far?

答:
It depends on what you do with that time.  I was in a similar spot a few years ago, burnt out on development, looking for a career change so I went back to school for a biology degree with an eye on med school.

Eventually I took a "temporary" job writing software for public health that became a long-term gig, and today I'm a CTO.

The thing I did that was smart was continuing to develop software while I was in school.  I wasn't one of those late-night hackers that worked on his pet project all the time (though I did take a summer off to work on something).  I learned Rails in that time, when it was still a young platform, and that has made all the difference for me today, having long-term experience with it.

Bottom line, the time off didn't hurt me.  It helped me rediscover what I liked about programming in the first place.  It also made me a more well-rounded person and developer.  Just don't waste the time and you'll do alright. (It helps to work on an open-source project or two just to have something to point at when they ask you what you've been doing the last couple of years.)

ContentLicense: CC BY-SA 2.5


问:
How to manage a large list of distinct numbers
I have a list of around 2 billion distinct numbers stored in memory for some computation.  Currently, every time I need to add a new entry I have to search the entire list for a potential duplicate.

I have 18 digit, 2 billion numbers to be stored in memory. Some of the numbers are repeated. So, I want to load new number in the memory and ignore if the number already exists. Right now, I append the number in the list if it does not exist already.

This process of linear scan of the already existing number is taking long time.  What can I do to get around this performance problem?

答:
Linear search of 2 billion numbers is going to be painful.  On average, you'll scan almost a billion numbers before finding the one you want.  Even if the numbers are in memory, that's got to take some time.

A better approach is to sort those numbers as you load them into memory and then use a Binary Search algorithm to quickly find the number you want in O(log n) time.

I'm not going to repeat Wikipedia's excellent write up of the algorithm here, but the general idea is to sample the middle of the list and compare it to the number you're looking for.  If your number is higher, you can immediately discard the smaller half of the list and try again with what's left.

Your first sample would either find the number or eliminate 1 billion numbers.

Your second sample would either find the number or eliminate 500 million numbers

Your 3rd sample would either find the number or reduce the search set to 250 million numbers.

... and so on.  As you can see, this converges on a solution (either the number is found or you know it's not there) very quickly.  There's the overhead of initially sorting the numbers, but that's peanuts compared to the time you'll save on the search.

If you can store the numbers on disk sorted, you'll be even that much more ahead of the game.


问:
Should an HTTP API always return a body?
Is there some sort of standard regarding HTTP API responses?

After reading this discourse thread I started to wonder.  We are developing our public HTTP JSON API at my work, and we do not return anything when it's not strictly needed (for example a PUT to /resource/{id} only returns 200 when OK or the corresponding 4XX or 5XX code, but no JSON body)

Should we return a generic {"success":true} like they discuss on that link above, or is it ok to return a "void" body and handle everything with http response codes?

答:
The base HTTP standard does not mandate that there be a document returned with a response.  For economy's sake, when an HTTP status conveys all that's required the body would be wasteful.  However, there are standards built on top of HTTP that add new rules.

There is an open JSON API standard that specifies:

A JSON object MUST be at the root of every JSON API response document. (italics represent what I added to clarify the text)

Unfortunately, the standard doesn't specify how to represent an empty document, and it is a work in progress.  At best I'd use it as a guideline.

Some applications (like ElasticSearch) provide a full JSON api, and always have some metadata so you can have a better idea of how the server is managing your data.  The standard response object tells you about the health of the index, if the request resulted in an error, how many nodes were affected, etc.  ElasticSearch uses "application/json" for the mime-type so it's unlikely they are applying the guidelines in the jsonapi.org standard.

JQuery and similar Javascript frameworks assume that there will always be a document.  The question is how much error checking do you want to force on your API consumers?  If you come up with a standard format for all responses that is only extended based on the type of request, you satisfy the need for a return document, and can facilitate easier debugging by your API consumers.


答:
I would not return simply a success status in the response, the HTTP error code only signals success or error. I'd only include the response itself to add detailed error information such as application-specific error codes or error messages.

For PUT, PATCH and POST requests you typically return the state of the resource after the request has been applied, not an empty response.

For POST requests that represent an action instead of simply creating a resource (not very RESTful, but still useful in practice), which doesn't have useful data to return, I'd return a response consisting of an empty JSON object, i.e. {}. That way the client gets a valid response and adding some information later on is unlikely to break it.

For DELETE requests returning 204 and an empty body is pretty common, which makes sense since the resource doesn't exist afterwards.

Title: Should an HTTP API always return a body?

Body:
Is there some sort of standard regarding HTTP API responses?

After reading this discourse thread I started to wonder.  We are developing our public HTTP JSON API at my work, and we do not return anything when it's not strictly needed (for example a PUT to /resource/{id} only returns 200 when OK or the corresponding 4XX or 5XX code, but no JSON body)

Should we return a generic {"success":true} like they discuss on that link above, or is it ok to return a "void" body and handle everything with http response codes?

ContentLicense: CC BY-SA 4.0


问:
Why is it a good practice to keep Javascript code in separate files?
In web development we are commonly used to keep Javascript code in separate files, but sometimes we need this Javascript code to manipulate server side data locally.

For example, making an Ajax Call to a dynamically created URL server side.

But some programmers My colleagues keep saying that plain Javascript in the JSP file is a sign of bad code, and wrong practices.

To what extent are they right ? Assuming that those blocks of code are not reusable in other pages, why is this practice perceived as a bad thing?

Edit :

Thanks for the quick answers, I'm still wondering how can I manage Dynamically created Javascript code (which cannot be cached, obviously). For example making an ajax call with an URL like this :

```<code>url : ${some_url_coming_from_server},
</code>```

In my case the code is huge, and I have server-data everywhere, am I doing it wrong ?

答:
@Mike and @X.L.Ant's answer already provide some excellent points.  I can provide one other point that hasn't been mentioned yet.

Ease of Editing & Tool Use - All kinds of things work better when you put your JS in a separate file.  Here are some examples:

JSHint/JSLint and other static code analysis tools

Code beautification like JSBeautify

Code uglification and minification like grunt-contrib-uglify

Syntax Highlighting


问:
Pattern for checking online service availability
I'm not sure that this is entirely on-topic, but I'll try to make it so.

I have an online service (API) and an Android application that uses it for all actions in the app. At the current moment, nothing is stored locally, so I have to depend on the API being online, and would like to warn the user when it's not (for whatever reason).

I'm wondering what the preferred method of checking availability is. As this is the first time I've ever done this, I've tried to do my research and have come up with three potential solutions:

1. Check availability on action

When the user takes an action, check the API's status. Currently I'm doing this (Java):

```<code>public class ServiceAvailability implements Runnable {

    private volatile boolean available;

    @Override
    public void run() {

        available = false;

        try {
            HttpURLConnection connection =
                    (HttpURLConnection) new URL("http://myservice.com").openConnection();
            connection.setConnectTimeout(3000);
            connection.setReadTimeout(1000);
            connection.setRequestMethod("HEAD");

            int responseCode = connection.getResponseCode();

            if (200 <= responseCode && responseCode <= 399) {
                available = true;
            }
        } catch (IOException exception) {
            exception.printStackTrace();
        }
    }

    public boolean isAvailable() {

        return available;
    }
</code>```

It works just fine. Just send a HTTP HEAD request to the site and see if the response is a good one. Every time the user takes an action (e.g., runs a search, clicks someone's profile, etc.) it calls the isAvailable() method, and displays an error message in the event that the available = false.

The advantage of this is that if the service goes down, the user will immediately know, and will be warned that they will not be able to use the app until the service is brought online again.

I can't think of any disadvantages of this at the moment...

2. Check availability on interval

The other solution (that I haven't actually implemented) is run a thread in the background and HTTP HEAD the service every X seconds/minutes and update the status accordingly; at that point, I could call isAvailable() which would simply return the boolean set by the result of the HEAD request.

The advantage to this is that a visual can be shown (for the duration) when the service is not online, letting the user know ahead of time that their request will not be processed.

The disadvantage that I see is that while HEAD requests are very minimal in the amount of bandwidth they use, 3G users with very little data or users with slow connections might have trouble sending the HEAD and receiving the response in a timely manner.

3. Combine the two

The last approach that I see is a combination, where the thread in the background checks availability every X seconds, and action methods using the API also check availability through an additional HEAD request.

The advantage that I see here is that the user will know (visually) when the service is offline for the duration, as well as have a fallback if the status of the API happens to change during the X seconds duration that the API was last checked.

From what I can see, the Facebook Messenger app (iOS at least) implements this. When you open the app, it 'attempts to connect' (visual up top) and if your connection drops, it will let you know with a bright red visual. Trying to take action when you're not connected (to their service) also gives you an error.

Question

Is there a single one of these 3 methods that are preferable, or a different method that I haven't mentioned? Furthermore, is there an actual design pattern for this (e.g., Singleton on a thread), one more preferable than what I've implemented?

Edit: As a user of the app myself, I feel that a pretty visual telling me that I won't be able to do something before I actually try is better than trying and failing. Furthermore, I want to implement this in order to determine more than just an 'up' or 'down' status of the API. For example, when the API is in maintenance for an update, I want to be able to receive a 503 and let the user know visually that the service is in maintenance mode, will be online shortly, and not to panic.

I'm not exactly sure how many users will be using the app in the long run, so I'm trying to prepare ahead of time in the event of API outages and maintenance. I don't have a large-scale infrastructure that can support millions of users like Facebook, so I believe that this availability check is reasonable in order to provide good (decent?) user experience, as I know for a fact that the API will not have 100% up-time. Not to mention that I'm the sole developer and the service might go down while I'm sleeping!

答:
I would Check Availability on Failed Action.  Just issue your calls normally and if you get a failure, then call the Service Availability function to verify.

Assume service is up, if one gets and error, then issue the additional call to verify availability.


答:
Just because a http-ping at time t gets a response, you've still got a large uncertainty that a request at time t' will complete.

I suggest you not ping the server if it can be avoided because it is a poor proxy measure of actual availability in the future. If a request is made and no response is received, retry with an exponential back-off interval.

Title: Pattern for checking online service availability

Body:
I'm not sure that this is entirely on-topic, but I'll try to make it so.

I have an online service (API) and an Android application that uses it for all actions in the app. At the current moment, nothing is stored locally, so I have to depend on the API being online, and would like to warn the user when it's not (for whatever reason).

I'm wondering what the preferred method of checking availability is. As this is the first time I've ever done this, I've tried to do my research and have come up with three potential solutions:

1. Check availability on action

When the user takes an action, check the API's status. Currently I'm doing this (Java):

```<code>public class ServiceAvailability implements Runnable {

    private volatile boolean available;

    @Override
    public void run() {

        available = false;

        try {
            HttpURLConnection connection =
                    (HttpURLConnection) new URL("http://myservice.com").openConnection();
            connection.setConnectTimeout(3000);
            connection.setReadTimeout(1000);
            connection.setRequestMethod("HEAD");

            int responseCode = connection.getResponseCode();

            if (200 <= responseCode && responseCode <= 399) {
                available = true;
            }
        } catch (IOException exception) {
            exception.printStackTrace();
        }
    }

    public boolean isAvailable() {

        return available;
    }
</code>```

It works just fine. Just send a HTTP HEAD request to the site and see if the response is a good one. Every time the user takes an action (e.g., runs a search, clicks someone's profile, etc.) it calls the isAvailable() method, and displays an error message in the event that the available = false.

The advantage of this is that if the service goes down, the user will immediately know, and will be warned that they will not be able to use the app until the service is brought online again.

I can't think of any disadvantages of this at the moment...

2. Check availability on interval

The other solution (that I haven't actually implemented) is run a thread in the background and HTTP HEAD the service every X seconds/minutes and update the status accordingly; at that point, I could call isAvailable() which would simply return the boolean set by the result of the HEAD request.

The advantage to this is that a visual can be shown (for the duration) when the service is not online, letting the user know ahead of time that their request will not be processed.

The disadvantage that I see is that while HEAD requests are very minimal in the amount of bandwidth they use, 3G users with very little data or users with slow connections might have trouble sending the HEAD and receiving the response in a timely manner.

3. Combine the two

The last approach that I see is a combination, where the thread in the background checks availability every X seconds, and action methods using the API also check availability through an additional HEAD request.

The advantage that I see here is that the user will know (visually) when the service is offline for the duration, as well as have a fallback if the status of the API happens to change during the X seconds duration that the API was last checked.

From what I can see, the Facebook Messenger app (iOS at least) implements this. When you open the app, it 'attempts to connect' (visual up top) and if your connection drops, it will let you know with a bright red visual. Trying to take action when you're not connected (to their service) also gives you an error.

Question

Is there a single one of these 3 methods that are preferable, or a different method that I haven't mentioned? Furthermore, is there an actual design pattern for this (e.g., Singleton on a thread), one more preferable than what I've implemented?

Edit: As a user of the app myself, I feel that a pretty visual telling me that I won't be able to do something before I actually try is better than trying and failing. Furthermore, I want to implement this in order to determine more than just an 'up' or 'down' status of the API. For example, when the API is in maintenance for an update, I want to be able to receive a 503 and let the user know visually that the service is in maintenance mode, will be online shortly, and not to panic.

I'm not exactly sure how many users will be using the app in the long run, so I'm trying to prepare ahead of time in the event of API outages and maintenance. I don't have a large-scale infrastructure that can support millions of users like Facebook, so I believe that this availability check is reasonable in order to provide good (decent?) user experience, as I know for a fact that the API will not have 100% up-time. Not to mention that I'm the sole developer and the service might go down while I'm sleeping!


问:
Using conditional feature compilation/inclusion for release versioning
I have been playing with the following idea: commonly when different release series (1.0.x, 1.1.x, development code) of a product are maintained in parallel one uses different branches within a version control system to develop them.  In theory though one could use feature macros (written from a C/C++ point of view, but the idea should be portable) to enable or disable particular features based on the version which is being built.  In C/C++ this would most likely mean enclosing code for new features in #ifdef FEATURE_X and either enabling or disabling them on the build command line or having a master header file containing code like

```<code>#if version > 101
# define FEATURE_X
# define FEATURE_Y
#endif
</code>```

Back-porting features, if one needs to do so, could be done by rearranging this file.

The idea behind this is that normally one will want to back-port fixes and improvements which are not part of significant new features to older versions unless one has a specific reason not to.  However, these back-ports are often done in a rather haphazard way, resulting in unintended subtle differences between versions or forgotten fixes in certain versions.  The feature macro approach reverses things, by making back-porting the default and explicitly marking code sections which are not for back-porting.  While it would not be a silver bullet by any means, it might improve the level of stability which one would achieve with a given amount of testing.  I would also expect it to improve code structure by forcing cleaner separation of different features.

So the question: does anyone know of real-world data about this or similar approaches?

答:
It is more common to use source control branching in order to control what features are available within a particular version of the software.

That said, applications that offer tiered functionality within the same version level will sometimes use the technique you describe.  Usually, you'll see two main uses of the conditional definitions.  The fist uses of the #defines declares the per-tier functionality for that tier's build.  The second usage is throughout the code where the per-tier functionality actually needs to be enabled.

In other cases, backwards compatibility on an otherwise breaking change can be maintained through the use of #defines and the application version.  This gets a bit more tricky and yields less easily maintained code, but is a convenient way of keeping all the relevant code together in a single branch.  The developer has to remember to revert the version number when making a special, backwards compatible build, but it does allow the older code to remain inline with the rest of the source code.


答:
It happens to be that service is your resource and for some reason it may not be available. What would you do if your client application talks directly to the database. Would you check availability of the database before trying to query it? I would not.

I think service not being available is an exceptional circumstance. I would expect my service to be available at all times, and if it's not, then something exceptionally bad happened and I will wait for client call to fail and exception to be thrown.

How will I handle exception is a different story. I might re-try calling the service, I might look at the type of exception to see if it's a timeout and service URI simply cannot be resolved.

What you have to think about is what value do you add to your program by checking for service's availability. Ok, you tell user that service is not available, but user probably doesn't care and if anything they probably get more frustrated as they might not know what service is. Don't bog them down with details, tell them that something went wrong and army of monkeys are working on it.


问:
Single instance of windows service querying multiple databases
My current situation is that we have four instances of a single windows service running on the server, for production, demo, QA and dev. I am looking for a solution where I just need to run single instance of the service that will hit all the above mentioned databases and process the data.

I know the purpose of having multiple databases (QA, dev etc.) is to do through testing and so I might have to install more than one instances. I am willing to install couple of instances (which is still less than 4 ) so that the maintenance is less.

But is there a way that a single windows service will do some sort of round robin technique and hit one database, do the processing, then hit the another database, do the processing and so on.

答:
Windows service is just a host for your application.

I may choose to write an application and host it in IIS process, or windows service, or console application, or WPF application. Point I'm making is that it does not matter if it's a windows service or not.

Your windows service can host an application that in turn queries multiple databases. It's just a host that can be started, stopped, paused, resumed and it offers some basic recovery out of the box.


问:
Does functional programming increase the 'representational gap' between problems and solutions?
Since machine language (e.g., 0110101000110101) computer languages have generally evolved to higher forms of abstraction, generally making it easier to understand the code when it's applied to a problem. Assembler was an abstraction over machine code, C was an abstraction over assembler, etc.

Object-oriented design seems to be very good at allowing us to model a problem in terms of objects, e.g., the problem of a university course registration system can be modeled with a Course class, a Student class, etc. Then, when we write the solution in an OO language, we have similar classes which get responsibilities and that generally is helpful for design, especially for modularizing the code. If I give this problem to 10 independent teams who solve it with an OO method, generally the 10 solutions will have the classes relating to the problem in common. There can be lots of differences when you start to get into coupling and interactions of those classes, so there's no such thing as "zero representational gap."

My experience with Functional Programming is very limited (no real-world use, only Hello World type programs). I'm failing to see how such languages allow easily mapping FP solutions to problems (with a low representational gap) the way OO languages do.

I understand the advantages of FP with respect to concurrent programming. But am I missing something, or is FP not about reducing a representational gap (making solutions easier to understand)?

Another way to ask this: would the FP code of 10 different teams solving the same real-world problem have a lot in common?

From Wikipedia on Abstraction (computer science) (emphasis mine):

Functional programming languages commonly exhibit abstractions related to functions, such as lambda abstractions (making a term into a function of some variable), higher-order functions (parameters are functions), bracket abstraction (making a term into a function of a variable).

The representational gap could be potentially increased, because [some] real-world problems aren't modeled easily with such abstractions.

Another way I see decreasing representational gap is in tracing the solution elements back to the problem. The 0's and 1s in machine code is very hard to trace back, whereas the Student class is easy to trace back. Not all OO classes trace easily to the problem space, but many do.

Don't FP abstractions always need explaining to find out which part of the problem space they are solving (apart from math problems)? OK - I'm good on this part. After looking at many more examples, I see how FP abstractions are very clear for parts of the problem that are expressed in data processing.

The accepted answer to a related question Can UML be used to model a Functional program? -- says "Functional programmers don't have a lot of use for diagrams." I really don't care if it's UML, but it makes me wonder about FP abstractions being easy to understand/communicate, if there are no diagrams that are widely used (assuming this answer is correct). Again, my level of FP use/understanding is trivial, so I understand no need for diagrams on simple FP programs.

OO design has function/class/package-levels of abstraction, with encapsulation (access control, information hiding) at each, which makes managing complexity easier. These are elements that allow going from the problem to the solution and back easier.

Many answers speak of how analysis and design are done in FP in a way analogous to OO, but nobody cites anything high-level so far (paul cited some interesting stuff, but it's low-level). I did a lot of Googling yesterday and found some interesting discussion. The following is from Refactoring Functional Programs by Simon Thompson (2004) (emphasis mine)

In designing an object-oriented system, it is taken for granted that design will
  precede programming. Designs will be written using a system like UML
  which is supported in tools such as Eclipse. Beginning programmers may
  well learn a visual design approach using systems like BlueJ. Work on a
  similar methodology for functional programming is reported in FAD: Functional Analysis and Design, but little
  other work exists. There may be a number of reasons for this.

Existing functional programs are of a scale which does not require design.
  Many functional programs are small, but others, such as the Glasgow Haskell
  Compiler, are substantial.

Functional programs directly model the application domain, thus rendering
  design irrelevant. Whilst functional languages provide a variety of powerful
  abstractions, it is difficult to argue that these provide all and only the
  abstractions needed to model the real world.

Functional programs are built as an evolving series of prototypes.

In the PhD thesis cited above, the benefits of using Analysis and design methodologies (ADM) are outlined independent of paradigms. But an argument is made that ADMs should align with the implementation paradigm. That is, OOADM works best for OO programming and is not well applied to another paradigm such as FP. Here's a great quote that I think paraphrases what I call representational gap:

one can argue at length regarding which paradigm
  provides the best support for software development, but one achieves the most natural,
  efficient and effective development package when one remains within a single paradigm
  from problem description through to implementation and delivery.

Here are the set of diagrams proposed by FAD:

function dependency diagrams which present a function with those it uses in its
  implementation;

type dependency diagram which provides the same service for types;
  and,

module dependency diagrams which present views of the module architecture of the system.

There's a case study in section 5.1 of the FAD thesis, which is a system to automate the production of data relating to a football (soccer) league. The requirements are 100% functional, e.g., input football results, produce league tables, scoring tables, attendance tables, transfer players between teams, updating data after new results, etc. No mention of how FAD works to solve non-functional requirements is documented, apart from stating that "new functionality should be allowed at a minimal cost", something that is nearly impossible to test.

Sadly, apart from FAD, I don't see any modern references for modeling languages (visual) that are proposed for FP. UML is another paradigm, so we should forget that.

答:
FP does indeed strive for a reduction in the representational gap:

Something you'll see a lot of in functional languages is the practice of building the language up (using bottom-up design) into an Embedded Domain Specific Language (EDSL). This lets you develop a means of expressing your business concerns in a way that is natural for your domain within the programming language. Haskell and Lisp both pride themselves on this.

Part (if not all) of what enables this ability is more flexibility and expressiveness within the base language(s) itself; with first class functions, higher-order functions, function composition, and in some languages, algebraic data types (AKA discriminated unions) and the ability to define operators*, there's more flexibility available for how to express things than there is with OOP, which means you'll probably find more natural ways to express things from your problem domain. (It should say something that many OOP languages have been adopting many of these features recently, if not starting out with them.)

* Yes, in many OOP languages you can override the standard operators, but in Haskell, you can define new ones!

In my experience working with functional languages (mostly F# and Haskell, some Clojure, and a little Lisp and Erlang), I have an easier time mapping the problem space down into the language than I do with OOP -- especially with algebraic data types, which I find more flexible than classes. Something that threw me for a loop when starting out with FP, particularly with Haskell, was that I had to think/work at a bit higher level than I was used to in imperative or OOP languages; you might be running into this a bit as well.


问:
Allow user to enter DSL, rules or code?
I have a python library that allows me to define rules by chaining inputs and outputs of functions ( producer(grep(count( [print(),log() ] )))
This functions define a pipeline from left to right.

How could I allow users to define pipelines from a UI ?

I need to take a definition like for example "producer->grep->count->print,log" and interpret it so as to call the former code.

Do i need a parser? an AST ? What would be a good way to build the call sequence fron a representation of the code?

答:
It really depends on the intended audience:

Are they programmers themselves or not? If they are, then providing an API  will be the easy way. You can also provide a DSL, but be wary that specifying and implementing a language might not be a trivial task and you can't actually go and change the syntax at every release. Bending the syntax of a programming language into a DSL might or might not work and, most importantly, might add uneeded complexity.

Are they accustomed to writing batch scripts or not? If they aren't, then you can forget a DSL, unless they are asking for it.

You don't actually know? What about some visual block programming backed by an API in your scripting language of choice? You could try Google Blocky:

Title: Allow user to enter DSL, rules or code?


问:
When to Use Shared Libraries
Note: I'm not sure if this question is more suitable for Stack Overflow or Programmers.  The thought process behind putting it here was that it doesn't actually relate to coding itself.

I noticed a small freeware utility I have on my computer uses a couple of DLLs.  From their names ("RenderAllChunks" and "RenderSlice"), it looks like they're being used just for specific functions.  If outsourcing program-specific functions is really necessary, wouldn't it be better to just stuff them in a separate header file?  It seems quite pointless to go through all the trouble of compiling, linking and distributing DLLs just for one function.

Is it bad to use shared libraries for small projects?

When/why are shared libraries preferable over static libraries (or even header files)?

答:
Dynamic libraries are good for drivers, because they use a standardized interface where the OS can hook right into the code and not bother with command line arguments and crazyness if it were an application instead.  For the same reason they're good for providing a common functionality to any program that wants to use it, such as Windows API DLLs.  Dynamic libraries should never be created for a single app, with the possible exception of plug-ins.

I personally dislike static libraries.  Since they're always loaded, they're taking up memory whether you're using them or not.  I suppose they're useful if you're using someone else's library and constantly making use of it in your code.

Title: When to Use Shared Libraries


问:
Garbage collection & memory leaks on hash tables
I was reading R. Read's How to be a programmer, and I came accross something I didn't understand:

...even with garbage collection, you can fill up all memory with
  garbage. A classic mistake is to use a hash table as a cache and
  forget to remove the references in the hash table. Since the reference
  remains, the referent is noncollectable but useless. This is called a
  memory leak. You should look for and fix memory leaks early. If you
  have long running systems memory may never be exhausted in testing but
  will be exhausted by the user.

So let's say I have a dictionary structure in python, indexed on md5 hashes (is this the kind of hashtable he's referring to?). Eg:

```<code>x = {}
x['c4ca4238a0b923820dcc509a6f75849b'] = 1
x['c81e728d9d4c2f636f067f89cc14862c'] = 2
</code>```

Can someone now walk me through his example? What do I have to do now concretely to cause a memory leak?

答:
It's pretty basic.  Walk through the code:

```<code>x = {}
</code>```

Memory reserved for overhead

```<code>x['c4ca4238a0b923820dcc509a6f75849b'] = 1
</code>```

Memory for one key/value pair allocated

```<code>x['c81e728d9d4c2f636f067f89cc14862c'] = 2
</code>```

Memory for two key/value pairs allocated

Now imagine we do this 10,000 times.  We will have allocated space for 10,000 key/value pairs.  Each hash added increases memory usage.  If these values will indeed never be used again, they are "useless", but since you've told python to save them, they will not be collected.  You'd need to remove the reference like this:

```<code>del x['c4ca4238a0b923820dcc509a6f75849b']
</code>```

You have to do this because in general, the garbage collector can't know that you are never going to look this value up.

The case talked about here is using a dictionary as a cache, and presumably you don't really know if you will need a particular value.  Also, presumably, there's no real limit to the number of values.  So with a long-running app, you could conceivably exhaust memory.  You'd need to have some scheme to delete elements from the cache when they are no longer needed, presumably by testing recency of use.

GC can't help you here any more than it can help you if you attempt to allocate a 100 gigabyte array.  You've told it explicitly through referencing not to discard any of the data.

Body:
It's pretty basic.  Walk through the code:

x = {}

Memory reserved for overhead

x['c4ca4238a0b923820dcc509a6f75849b'] = 1

Memory for one key/value pair allocated

x['c81e728d9d4c2f636f067f89cc14862c'] = 2

Memory for two key/value pairs allocated

Now imagine we do this 10,000 times.  We will have allocated space for 10,000 key/value pairs.  Each hash added increases memory usage.  If these values will indeed never be used again, they are "useless", but since you've told python to save them, they will not be collected.  You'd need to remove the reference like this:

del x['c4ca4238a0b923820dcc509a6f75849b']

You have to do this because in general, the garbage collector can't know that you are never going to look this value up.

The case talked about here is using a dictionary as a cache, and presumably you don't really know if you will need a particular value.  Also, presumably, there's no real limit to the number of values.  So with a long-running app, you could conceivably exhaust memory.  You'd need to have some scheme to delete elements from the cache when they are no longer needed, presumably by testing recency of use.

GC can't help you here any more than it can help you if you attempt to allocate a 100 gigabyte array.  You've told it explicitly through referencing not to discard any of the data.


问:
What is the definition of user classes, with respect to software use?
I'm writing the Software Requirement Specification document for a piece of software that I am developing. A part of the SRS is the identification of the user class.

Can somebody please give or refer me to definition of a user class as it relates to a software product?

答: What you want to do is to identify the various user classes that you anticipate will use this product/system. User classes may be differentiated based on frequency of use, subset of product functions used, technical expertise, security or privilege levels, educational level, or experience.</p>


答:
In addition to what others have said, it's also possible for an exception to be thrown inside the catch clause. Consider this:

```<code>try {
    throw new SomeException();
} catch {
    DoSomethingWhichUnexpectedlyThrows();
}
Cleanup();
</code>```

In this example, the Cleanup() function never runs, because an exception gets thrown in the catch clause and the next highest up catch in the call stack will catch that. Using a finally block removes this risk, and makes the code cleaner to boot.

Title: Is the 'finally' portion of a 'try ... catch ... finally' construct even necessary?

Body: Some languages (such as C++ and early versions of PHP) don't support the finally part of a try ... catch ... finally construct. Is finally ever necessary? Because the code in it always runs, why wouldn't/shouldn't I just place that code after a try ... catch block without a finally clause? Why use one? (I'm looking for a reason/motivation for using/not using finally, not a reason to do away with 'catch' or why it's legal to do so.)

Body:
In addition to what others have said, it's also possible for an exception to be thrown inside the catch clause. Consider this:

try {
    throw new SomeException();
} catch {
    DoSomethingWhichUnexpectedlyThrows();
}
Cleanup();

In this example, the Cleanup() function never runs, because an exception gets thrown in the catch clause and the next highest up catch in the call stack will catch that. Using a finally block removes this risk, and makes the code cleaner to boot.


问:
Is it safe to install TortoiseSVN on production servers?
Small shop, few production servers, no test or development servers, all Win2k3 WEB based.

There is a need to keep versioned files on one of the machines. Is TortoiseSVN safe against exploitability, does it need extra hardening? Any known license problems, incompatibilities?

答: I too agree that this is not good practice to have a repository on a production server.  So you are going to version the files on the development machine and version the files on the production server?  If you have that much time on your hands to do double the work, they aren't giving you enough work my friend.  This is what the development machine is used for to develop the code, version the code, track changes, test changes, ..... THEN DEPLOY TO PRODUCTION machine.  Everything on the production machine is working code if you use your development machine correctly.</p>


答:
You could use a hash table using the number itself as the key.

This means lookups and insertions would both be constant in time. If you know you have approximately two billion records you can pre-allocate that much space ahead of time so resizing is not an issue.

Title: How to manage a large list of distinct numbers

Body:
I have a list of around 2 billion distinct numbers stored in memory for some computation.  Currently, every time I need to add a new entry I have to search the entire list for a potential duplicate.

I have 18 digit, 2 billion numbers to be stored in memory. Some of the numbers are repeated. So, I want to load new number in the memory and ignore if the number already exists. Right now, I append the number in the list if it does not exist already.

This process of linear scan of the already existing number is taking long time.  What can I do to get around this performance problem?


问:
What was your most difficult bug hunt and how did you find it and kill it?
This is a "Share the Knowledge" question. I am interested in learning from your successes and/or failures.

Information that might be helpful...

Background:

Context: Language, Application,
Environment, etc.

How was the bug identified ?

Who or what identified the bug ?

How complex was reproducing the bug ?

The Hunting.

What was your plan  ?

What difficulties did you encounter ?

How was the offending code finally found ?

The Killing.

How complex was the fix ?

How did you determine the scope of the fix ?

How much code was involved in the fix ?

Postmortem.

What was the root cause technically ? buffer overrun, etc.

What was the root cause from 30,000 ft ?

How long did the process ultimately take ?

Were there any features adversely effected by the fix ?

What methods, tools, motivations did you find particularly helpful ? ...horribly useless ?

If you could do it all again
?............

These examples are general, not applicable in every situation and possibly useless. Please season as needed.

答:
For an University project we were writing an Distributed P2P Nodes system that share files, this supported multicasting to detect each other, multiple rings of nodes and a nameserver so a node is assigned to a client.

Written in C++ we used POCO for this as it allows nice IO, Socket and Thread programming.

There were two bugs that arise that annoyed us and made us lose a lot of time, a really logic one:

Randomly, a computer was sharing his localhost IP instead of it's remote IP.

This caused clients to connect to the node on the same PC or nodes to connect with themselves.

How did we identify this? When we improved the output in the nameserver we discovered at a later moment when we rebooted the computers that our script to determine the IP to give was wrong. Randomly, the lo device was listed first instead of the eth0 device... Really stupid. So now we hardcoded to requist it from eth0 as this is shared among all university computers...

And now a more annoying one:

Randomly, the packet flow would randomly pause.

When the next client connects it would continue...

This happened really random and as more than one computer is involved it got more annoying to debug this problem, the university computers do not allow us to run Wireshark on those so we are left with guessing if the problem was at the sending side or the receiving side.

With a lot of output in the code we just took the assumption that sending the commands goes fine,

this left us wondering where the real problem was... It seemed that the way POCO polls is wrong and that we instead should check for available characters on the incoming socket.

We took the assumption that this worked as more simpler tests in a prototype involving less packets didn't cause this issue, so this caused us to just assume that the poll statement was working but... It wasn't. :-(

Lessons learned:

Don't make stupid assumptions like the order of the network devices.

Frameworks don't always do their job (either implementation or documentation) right.

Provide enough output in the code, if not allowed there be sure to log extended details to a file.

When code hasn't been unit tested (because it's too difficult) don't assume things to work.


问:
Any reasons NOT to write self testing Python code?
Whilst writing tests I was giving considerable thought to the question of how to ensure I have tests for every class in my application.

It occurred to me that maybe I should just put the test code into the classes, thereby making it obvious that each class has a test and vice versa.

I found that this is called "self testing code" http://en.wikipedia.org/wiki/Self-testing_code

So of course in software development there's always going to be plenty of people who say THAT'S A TERRIBLE WAY TO PROGRAM, YOU CAN'T DO THAT! I'm interested in hearing what the naysayers have to say about writing self testing classes in Python. What are the reasons its a bad idea?

thanks!

```<code>class MyOperation():

    def some_useful_function(self):
         # do some useful function

    def some_other_function(self):
         # do some other function

    class Test_MyOperation():

        def test_something(self):
            # some test code
            assert(True)

        def test_something_else(self):
            # some more test code
            assert(True)
</code>```

答:
Here are four reasons not to do it:

Anyone who reads your code will need to wade through lots of test code.  This will make it harder to figure out what it is doing.

All of the test code gets loaded into memory even when you are not testing.  This is wasteful.  (Perhaps not important in these days when 8 GB RAM is normal.)

Test code should have exactly the access that other users of the code has.  If it is part of the class itself, you make miss things as your test code isn't running in the same context as actual code using the class.  (A bigger problem in languages like C++ that enforce privacy but still it can cause issues.)

It will make code coverage tools inaccurate

The alternative I've used is to put all test code for foo.py in a file named test/test_foo.py.  This makes it trivial to automatically run a test for a given file, and to see what test code applies to what file, without having any of these issues.  It also becomes very natural to have an editor with a split window view, one in the real code, one in the test code.


问:
Why does this implementation of Dijkstra's algorithm work in O(n^2)?
Here is the code I use for implementing Dijkstra's algorithm. Consider a graph with n vertices and m edges. Shouldn't it run in O(n^2 m) ? Someone may say that there are n vertices and each edge gets processed once, therefore it is O(n m). But the while loop can run at most n times, the 1st for loop at most n times and the second for loop at most m times. Therefore, this should be an O(n^2 m) implementation.

Here X is a vector, head[] and shortest[] are arrays.

```<code>X.push_back(1);
head[1] = true;

while(X.size()!=MAX) {
    min = INT_MAX;

    for(j=0;j<X.size();j++) {
        node = X[j];

        for(k=0;k<graph[node].size();k++) {
            v = graph[node][k];

            if(head[v]==true)
                continue;

            if(min>(weight[node][k]+shortest[node])) {
                pos = v;
                min = weight[node][k]+shortest[node];
            }
       }
  }

  shortest[pos] = min;
  head[pos] = true;

  X.push_back(pos);
}
</code>```

答:
Now, I'm not well-versed in graph algorithms but I don't think your code implements Dijkstra's algorithm correctly.  Your code as it stands will check vertices more than once, which is not what a correct implementation should do.

In Dijkstra's algorithm, one keeps track of a set of unvisited vertices so as to avoid re-checking vertices that have already been checked.  Your code keeps track of a set of visited vertices, which doesn't make any sense.


问:
Displaying copyright notice for OSS in closed source Android app
I am considering the usage of various open source libraries in a closed source Android app. The libraries are released under various licenses (MIT, BSD modern, Apache 2.0) which allow this kind of usage, but require that the copyright notice is made available verbatim with the application.

I have seen various approaches, at least four:

A submenu triggers a dialog where project names and relative licenses are displayed, e.g. Google apps.

A message like "This app uses various projects released under license XXXX" is displayed on the app website. No notice is present inside the application or in the Play Store description, e.g. Whatsapp.

No mention is done of the libraries being distributed with the application.

Like 3, but the APK contains a /license folder.

What is the best practice? Maybe something else? Are approaches #2 and #3 even in compliance?

As a passionate contributor to various open source projects, I would really go with #1. Unfortunately, I am not in charge, so I must be able to argue about #2 and #3 too and/or propose a better solution.

答:
A message like "This app uses various projects released under license XXXX" is displayed on the app website. No notice is present inside the application...

It’s moot whether BSD licenses allow that, but I could not imagine how the following clause from both MIT licenses (Expat and X11) could be read to make that possible:

The above copyright notice and this permission notice shall be included
  in all copies or substantial portions of the Software.


答:
Use a set.

It has many of the semantic properties of list, but only stores unique values.  To be honest, I have am unsure if it will perform reasonably for billions of elements, but it is backed by hash tables, and I have successfully used it to do unions and intersections of sets with over 10 million entries.


问:
How useful are IT headhunters/recruiters when looking for a new job?
Since they exist for several fields with varying degrees of usefulness, I'm curious as to the reputation of headhunters/recruiters that focus solely on IT professionals (e.g. programmers, software engineers, CIOs, etc) when it comes to finding a new job.

Are they actually useful or is it fairly hit or miss? Does the old adage of only working with a limited number apply or can you safely give you resume/CV to several of them?

答:
I got one job through a recruiter 12 years ago. Since then, nothing. I find them to be annoying at best. On monster.com I've noted that I prefer email, but they call. They are looking for a Python programmer, but the job turns out to be mostly C++ with a bit of Python, maybe. It's for a permanent position in London, I don't live in London and ain't gonna move, which is noted on my profile, etc, etc.

Most recruiters seem to work with a scattergun approach. They contact as many as possible, they build up a list of CV's which they want to list everything I've even done no matter how irrelevant it is for what I know. I'm a Python guru, but they want to hire me to do Java jobs.

Obviously there are good recruiters. They are just very far between.


答:
It is hard to say what you'd need to do internally within your service to make this work but what you are building here is effectively a multi-tenant operation inside your service. You are adding an account name parameter that needs to somehow map to an instruction as to which database to use. It actually is pretty straightforward if you've got good dependency injection in place and you have a fixed number of tenants.

This won't quite eliminate the need for a full development version -- unless you want to get into some very fancy footwork with keeping multiple versions of databases and objects straight somehow.

As for the value it depends on what you are doing with it. I've used this sort of setup very successfully in some scenarios where we had consumers that would want to consume and test against different versions of data within the same structure. But building it out had a bit of overhead so I wouldn't do it for the wrong reasons. All in all a better way forward might be to take the pain out of deployment rather than build your app up to multi-tenancy. Especially if there are code differences between dev/qa and production.

Title: Single instance of windows service querying multiple databases

Body:
My current situation is that we have four instances of a single windows service running on the server, for production, demo, QA and dev. I am looking for a solution where I just need to run single instance of the service that will hit all the above mentioned databases and process the data.

I know the purpose of having multiple databases (QA, dev etc.) is to do through testing and so I might have to install more than one instances. I am willing to install couple of instances (which is still less than 4 ) so that the maintenance is less.

But is there a way that a single windows service will do some sort of round robin technique and hit one database, do the processing, then hit the another database, do the processing and so on.


问:
Is the 'finally' portion of a 'try ... catch ... finally' construct even necessary?
Some languages (such as C++ and early versions of PHP) don't support the finally part of a try ... catch ... finally construct. Is finally ever necessary? Because the code in it always runs, why wouldn't/shouldn't I just place that code after a try ... catch block without a finally clause? Why use one? (I'm looking for a reason/motivation for using/not using finally, not a reason to do away with 'catch' or why it's legal to do so.)

答:
Since this question doesn't specify C++ as a language I'll consider a mix of C++ and Java, since they take a different approach to object destruction, which is getting suggested as one of the alternatives.

Reasons you might use a finally block, rather than code after the try-catch block

you return early from the try block: Consider this

```<code>Database db = null;
try {
 db = open_database();
 if(db.isSomething()) {
   return 7;
 }
 return db.someThingElse();
} finally {
  if(db!=null)
    db.close();
}
</code>```

compared with:

```<code>Database db = null;
int returnValue = 0;
try {
 db = open_database();
 if(db.isSomething()) {
   returnValue = 7;
 } else {
   returnValue = db.someThingElse();
 }
} catch(Exception e) {
  if(db!=null)
    db.close();
}
return returnValue;
</code>```

you return early from the catch block(s) :  Compare

```<code>Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  return 7;
} catch (DBIsADonkeyException e ) {
  return 11;
} finally {
  if(db!=null)
    db.close();
}
</code>```

vs:

```<code>Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  if(db!=null)
    db.close();
  return 7;
} catch (DBIsADonkeyException e ) {
  if(db!=null)
    db.close();
  return 11;
}
db.close();
</code>```

You rethrow exceptions. Compare:

```<code>Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  throw convertToRuntimeException(e,"DB was wonkey");
} finally {
  if(db!=null)
    db.close();
}
</code>```

vs:

```<code>Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  if(db!=null)
    db.close();
  throw convertToRuntimeException(e,"DB was wonkey");
}
if(db!=null)
  db.close();
</code>```

These examples don't make it seem too bad, but often you have several of these cases interacting and more than one exception/resource type in play. finally can help keep your code from becoming a tangled maintenance nightmare.

Now in C++ these can be handled with scope based objects. But IMO there are two disadvantges to this approach 1. syntax is less friendly. 2. Order of construction being the reverse of order of destruction can make things less clear.

In Java you can't hook the finalize method to do your cleanup since you don't know when it will happen - (well you can but thats a path filled with fun race conditions - JVM has a lot of scope in deciding when it destroys things - often its not when you expect it - either earlier or later than you might expect - and that can change as the hot-spot compiler kicks in... sigh...)

Body:
Since this question doesn't specify C++ as a language I'll consider a mix of C++ and Java, since they take a different approach to object destruction, which is getting suggested as one of the alternatives.

Reasons you might use a finally block, rather than code after the try-catch block

you return early from the try block: Consider this

Database db = null;
try {
 db = open_database();
 if(db.isSomething()) {
   return 7;
 }
 return db.someThingElse();
} finally {
  if(db!=null)
    db.close();
}

compared with:

Database db = null;
int returnValue = 0;
try {
 db = open_database();
 if(db.isSomething()) {
   returnValue = 7;
 } else {
   returnValue = db.someThingElse();
 }
} catch(Exception e) {
  if(db!=null)
    db.close();
}
return returnValue;

you return early from the catch block(s) :  Compare

Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  return 7;
} catch (DBIsADonkeyException e ) {
  return 11;
} finally {
  if(db!=null)
    db.close();
}

vs:

Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  if(db!=null)
    db.close();
  return 7;
} catch (DBIsADonkeyException e ) {
  if(db!=null)
    db.close();
  return 11;
}
db.close();

You rethrow exceptions. Compare:

Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  throw convertToRuntimeException(e,"DB was wonkey");
} finally {
  if(db!=null)
    db.close();
}

vs:

Database db = null;
try {
 db = open_database();
 db.doSomething();
} catch (DBIntegrityException e ) {
  if(db!=null)
    db.close();
  throw convertToRuntimeException(e,"DB was wonkey");
}
if(db!=null)
  db.close();

These examples don't make it seem too bad, but often you have several of these cases interacting and more than one exception/resource type in play. finally can help keep your code from becoming a tangled maintenance nightmare.

Now in C++ these can be handled with scope based objects. But IMO there are two disadvantges to this approach 1. syntax is less friendly. 2. Order of construction being the reverse of order of destruction can make things less clear.

In Java you can't hook the finalize method to do your cleanup since you don't know when it will happen - (well you can but thats a path filled with fun race conditions - JVM has a lot of scope in deciding when it destroys things - often its not when you expect it - either earlier or later than you might expect - and that can change as the hot-spot compiler kicks in... sigh...)


问:
Capturing mobile device system (output) audio
I'm trying to figure out a way to capture the system audio of an Android and/or Windows Phone. The idea is to provide a stream based on the music I'm currently playing on my phone.

What I'm not sure about is what the best approach would be for sending the audio. Preferably I'd like to capture all the device audio (same as when connected to a bluetooth device). But I'm not sure whether this is possible with Android or Windows Phone.

For Android I found this article http://xzpeter.org/?p=254, he states this is'nt possible without making your own Android build. Which isn't an option for me.

For Windows Phone I can only find ways to capture audio from the mic. Not directly from the system.

The only alternative I can come up with is to let the app provide all the audio, meaning I would have to build all the basic mediaplayer functionality into the app. But this would mean I have to put much more work into the app, and I wouldn't be able to use other apps like Winamp and YouTube to provide audio.

Did I maybe overlook a way to capture all the audio of the device? Or maybe there's a way to capture audio from specific applications?

Edit

After doing some more research, I really doubt I can capture all system audio. Or maybe it's possible to simulate an bluetooth audio device?

For the Windows Phone I was going for the alternative solution: selecting songs which would then be streamed to the server. But it seems that for Windows Phone it's not even possible to get physical access to the songs: https://stackoverflow.com/questions/16251400/stream-a-xna-framework-media-song-to-a-server

答:
Here is a potential partial solution, though not really a programming solution.

Assuming the goal is specifically to have the audio of a music file from your mobile device play on another device, for example, a PC or server, you might try the OnAir player, which has apps for mobile devices, some televisions, and Mac/Linux/Windows computers.

If you have further processing to do with the audio, you an probably set up your computer to capture the audio and redirect it.

You don't state your final goal for the audio or what kind of server you are using for streaming, but here's a theoretical example setup:

I could run the app on my Android phone, streaming to my Linux PC. Pulse Audio (default on Ubuntu Linux) allows output capture, so I could write a program to receive the audio and redirect it to the input of a streaming program.

This would only cover the music you are playing from OnAir of course; none of the other sounds would come through (such as SMS and email notifications or the phone ringing).

Also note (as my second link points out): be careful with copyright restrictions on the audio. If you don't own the content and are streaming to other people you can get into trouble.

References:

onAir: http://www.onairplayer.com/onair.html

Capturing audio in Linux: http://manual.audacityteam.org/o/man/tutorial_recording_computer_playback_on_linux.html


答:
As you've apparently already surmised, yes, C++ provides the same capabilities without that mechanism. As such, strictly speaking, the try/finally mechanism is not really necessary.

That said, doing without it does impose some requirements on the way the rest of the language is designed. In C++ the same set of actions is embodied in a class' destructor. This works primarily (exclusively?) because destructor invocation in C++ is deterministic. This, in turn, leads to some rather complex rules about object lifetimes, some of which are decidedly non-intuitive.

Most of the other languages provide some form of garbage collection instead. While there are things about garbage collection that are controversial (e.g., its efficiency relative to other methods of memory management) one thing generally isn't: the exact time when an object will be "cleaned up" by the garbage collector is not tied directly to the scope of the object. This prevents its use when cleanup needs to be deterministic either when it's simply required for correct operation, or when dealing with resources so precious that their cleanup most not be delayed arbitrarily. try/finally provides a way for such languages to deal with those situations that require that deterministic cleanup.

I think those claiming that C++ syntax for this capability is "less friendly" than Java's are rather missing the point. Worse, they're missing a much more crucial point about the division of responsibility that goes far beyond syntax, and has a great deal more to do with how code is designed.

In C++, this deterministic cleanup happens in the object's destructor. That means the object can be (and normally should be) designed to clean up after itself. This goes to the essence of object oriented design--a class should be designed to provide an abstraction, and enforce its own invariants. In C++, one does precisely that--and one of the invariants for which it provides is that when the object is destroyed, the resources controlled by that object (all of them, not just memory) will be destroyed correctly.

Java (and similar) are somewhat different. While they do (sort of) support a finalize that could theoretically provide similar capabilities, the support is so weak that it's basically unusable (and in fact, essentially never used).

As a result, rather than the class itself being able to do the required cleanup, the client of the class needs to take steps to do so. If we do a sufficiently short-sighted comparison, it can at first glance appear that this difference is fairly minor and Java is quite competitive with C++ in this respect. We end up with something like this. In C++, the class looks something like this:

```<code>class Foo {
    // ...
public:
    void do_whatever() { if (xyz) throw something; }
    ~Foo() { /* handle cleanup */ }
};
</code>```

...and the client code looks something like this:

```<code>void f() {
    Foo f;
    f.do_whatever();
    // possibly more code that might throw here
}
</code>```

In Java we exchange a little more code where the object is used for a little less in the class. This initially looks like a pretty even trade-off. In reality, it's far from it though, because in most typical code we only define the class in one place, but we use it many places. The C++ approach means we only write that code to handle the cleanup in one place. The Java approach means we have to write that code to handle the cleanup many times over, in many places--every place we use an object of that class.

In short, the Java approach basically guarantees that many abstractions we try to provide are "leaky"--any and every class that requires deterministic cleanup obliges the client of the class to know about the details of what to cleanup and how to do the cleanup, rather than those details being hidden in the class itself.

Although I've called it "the Java approach" above, try/finally and similar mechanisms under other names aren't entirely restricted to Java. For one prominent example, most (all?) of the .NET languages (e.g., C#) provide the same.

Recent iterations of both Java and C# also provide something of a halfway point between "classic" Java and C++ in this regard. In C#, an object that wants to automate its cleanup can implement the IDisposable interface, which provides a Dispose method that's (at least vaguely) similar to a C++ destructor. While this can be used via a try/finally like in Java, C# automates the task a little more with a using statement that lets you define resources that will be created as a scope is entered, and destroyed when the scope is exited. Though still well short of the level of automation and certainty provided by C++, this is still a substantial improvement over Java. In particular, the class designer can centralize the details of how to dispose of the class in its implementation of IDisposable. All that's left for the client programmer is the lesser burden of writing a using statement to assure that the IDisposable interface will be used when it should be. In Java 7 and newer, the names have been changed to protect the guilty, but the basic idea is basically identical.

Body:
As you've apparently already surmised, yes, C++ provides the same capabilities without that mechanism. As such, strictly speaking, the try/finally mechanism is not really necessary.

That said, doing without it does impose some requirements on the way the rest of the language is designed. In C++ the same set of actions is embodied in a class' destructor. This works primarily (exclusively?) because destructor invocation in C++ is deterministic. This, in turn, leads to some rather complex rules about object lifetimes, some of which are decidedly non-intuitive.

Most of the other languages provide some form of garbage collection instead. While there are things about garbage collection that are controversial (e.g., its efficiency relative to other methods of memory management) one thing generally isn't: the exact time when an object will be "cleaned up" by the garbage collector is not tied directly to the scope of the object. This prevents its use when cleanup needs to be deterministic either when it's simply required for correct operation, or when dealing with resources so precious that their cleanup most not be delayed arbitrarily. try/finally provides a way for such languages to deal with those situations that require that deterministic cleanup.

I think those claiming that C++ syntax for this capability is "less friendly" than Java's are rather missing the point. Worse, they're missing a much more crucial point about the division of responsibility that goes far beyond syntax, and has a great deal more to do with how code is designed.

In C++, this deterministic cleanup happens in the object's destructor. That means the object can be (and normally should be) designed to clean up after itself. This goes to the essence of object oriented design--a class should be designed to provide an abstraction, and enforce its own invariants. In C++, one does precisely that--and one of the invariants for which it provides is that when the object is destroyed, the resources controlled by that object (all of them, not just memory) will be destroyed correctly.

Java (and similar) are somewhat different. While they do (sort of) support a finalize that could theoretically provide similar capabilities, the support is so weak that it's basically unusable (and in fact, essentially never used).

As a result, rather than the class itself being able to do the required cleanup, the client of the class needs to take steps to do so. If we do a sufficiently short-sighted comparison, it can at first glance appear that this difference is fairly minor and Java is quite competitive with C++ in this respect. We end up with something like this. In C++, the class looks something like this:

class Foo {
    // ...
public:
    void do_whatever() { if (xyz) throw something; }
    ~Foo() { /* handle cleanup */ }
};

...and the client code looks something like this:

void f() {
    Foo f;
    f.do_whatever();
    // possibly more code that might throw here
}

In Java we exchange a little more code where the object is used for a little less in the class. This initially looks like a pretty even trade-off. In reality, it's far from it though, because in most typical code we only define the class in one place, but we use it many places. The C++ approach means we only write that code to handle the cleanup in one place. The Java approach means we have to write that code to handle the cleanup many times over, in many places--every place we use an object of that class.

In short, the Java approach basically guarantees that many abstractions we try to provide are "leaky"--any and every class that requires deterministic cleanup obliges the client of the class to know about the details of what to cleanup and how to do the cleanup, rather than those details being hidden in the class itself.

Although I've called it "the Java approach" above, try/finally and similar mechanisms under other names aren't entirely restricted to Java. For one prominent example, most (all?) of the .NET languages (e.g., C#) provide the same.

Recent iterations of both Java and C# also provide something of a halfway point between "classic" Java and C++ in this regard. In C#, an object that wants to automate its cleanup can implement the IDisposable interface, which provides a Dispose method that's (at least vaguely) similar to a C++ destructor. While this can be used via a try/finally like in Java, C# automates the task a little more with a using statement that lets you define resources that will be created as a scope is entered, and destroyed when the scope is exited. Though still well short of the level of automation and certainty provided by C++, this is still a substantial improvement over Java. In particular, the class designer can centralize the details of how to dispose of the class in its implementation of IDisposable. All that's left for the client programmer is the lesser burden of writing a using statement to assure that the IDisposable interface will be used when it should be. In Java 7 and newer, the names have been changed to protect the guilty, but the basic idea is basically identical.


问:
Would one use a 2D Gaming Engine for a desktop application?
I am thinking about a library that I could use for a program to create presentations but I am not sure what one could/should use for a task like that.

What first came to my mind are 2D Gaming Engines that could be used for rendering etc. for a desktop application as well. But would one do something like that?

I don't want to reinvent the wheel here and there does not seem to exist something like a "2D Desktop Application Graphic Engine".

Does anybody have experience with something like that matter?

答:
No, don't use a gaming engine. They are typically designed for performance while sacrificing accuracy and also often push the CPU/GPU much harder than you want creating excessive heat and power/battery consumption.

There are "2D Desktop Application Graphic Engines" available, for example I'm an OS X/iOS developer where we have Quartz and Core Animation. They are specifically designed for high performance rendering of user interface elements.

I'm less familiar with other platforms, but I'm confidant they have equivalent engines available.

As others have suggested, using HTML/CSS is another good option that is very popular, especially if you are displaying a lot of content on a wide variety of screen sizes. It's also completely cross platform.


答:
If your only goal is to reduce maintenance efforts, I suggest instead of making such a major architectural change to your service, add some tools which allow you to manage the four instances "as one". For example:

starting and stopping of all four instances at once: can be accomplished by start and stop scripts

backing up any data written by your services: just the same, some scripts will do it

producing one log instead of many: make sure your services use standard windows logging mechanics which pipes all logging output of different processes into the standard system or application log

using just one configuration file for all four services instead of four files: put parameters like the DB connection (which must be different for your four use cases) into different sections for QA, dev, test, production inside the configuration file, and separate those from parameters which are the same for all instances. Or, keep using different config files and provide an include mechanism to import config parameters equal for all instances from a shared file.

and if your services need more maintenance tasks, you could even bundle that by creating a special management tool, maybe a command line tool, maybe a tool with a GUI, which makes the maintenance easier.

I guess that will be less effort than merging all the instances into one, and still leaves you in a position with all the benefits you have from four different instances now, like starting and stopping them individually, providing different versions of your program for testing and production, making sure a crash of the testing instance does not affect production, and so on.


答:
All that is logicaly  "necessary" in a programming language are the instructions:

```<code>assignment a = b
subtract a from b
goto label
test a = 0
if true goto label
</code>```

Any algorithm can be implemented using only the instructions above, all other language constructs are there to make programs easier to write and more understandable to other programmers.

See oldie worldy computer for actual hardware using such a minimal instruction set.

Body:
All that is logicaly  "necessary" in a programming language are the instructions:

assignment a = b
subtract a from b
goto label
test a = 0
if true goto label

Any algorithm can be implemented using only the instructions above, all other language constructs are there to make programs easier to write and more understandable to other programmers.

See oldie worldy computer for actual hardware using such a minimal instruction set.


问:
Why does this algorithm work in O(n m)?
This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m)

This is a graph problem, where we are supposed to find the number of ways to traverse from a to c.
Note that only the paths like a-->b-->c and a-->d-->c need to be considered. That is, there should be a difference of only one node, in between them.

n is the number of vertices, m is the number of edges and nxt is the adjacency list.

Let's iterate through all combinations of a and c just two simple
  nested loops in O(n^2) and find all candidates for b and d inside. To
  find candidates you can go through all neighbors of a and check that
  they are neighbors of c. Among all the candidates you should choose
  two junctions as b and d. So just use
  https://en.wikipedia.org/wiki/Combination All you need is to add to
  the answer , where r is the number of candidates (common neighbors of
  a and c). The code is:

```<code>for (int a = 0; a < n; a++)
    for (int c = 0; c < n; c++)
        if (a != c)
        {
            int r = 0;
            for (int b = 0; b < nxt[a].size(); b++)
                if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c])
                    r++;
            result += r * (r - 1) / 2;
        }
</code>```

It is easy to see that the total complexity is O(nm), because of sum of number of neighbors over all junctions is exactly m.

If there are 3 loops involved, then how can the worst case complexity be O(n m)

答:
The outer loop has n iterations.

The middle loop has n iterations.

The inner loop has deg(a) iterations. This is because the nxt array is adjacency list of the graph, which means nxt[a] is a list of all edges going from vertex a and therefore nxt[a].size() is (out) degree of a.

Because m, the number of edges, is ∑a deg(a), the inner two loops together make m iterations and times the outer n is the result.

Notes: The test whether edge from nxt[a][b] to c exists is O(1), because g is incidence matrix. It is a bit unusual to see both adjacency list and incidence graph representations, because they both have to be prepared. The usual approach is to use adjacency list for sparse graphs, i.e. those with m ~ O(n), because then deg(a) ~ O(1) and linear search in the for the follow-up edge is constant-time, and to use incidence matrix for dense graphs, i.e. those with m ~O(n2), because then the O(n m) = O(n3) anyway, so looping over all vertices instead of out edges in the inner loop does not matter.

The other issue is that the author of this should be condemned for the choice of variables. It is usual for mathematical algorithms to use single-letter variables, but at least variable indicating index into the adjacency list should not be taken from the same range as variables for vertices. I'd use customary u and v for vertices (that is u = a and v = c) and i for index (that is i = b).

Title: Why does this algorithm work in O(n m)?


问:
Is factory pattern a right pattern for the situation described here?
Is factory pattern a right pattern when we want to consolidate the related objects?

Problem - In the Set-top box, I have a user-io, basically the interface to control the settop box - The user-io can be rcu i.e. remote control, front panel - the buttons on the Set-top box, and the rear-rcu - this is used for testing the bunch of settop boxes.

Solution -  A factory object that checks whether the user-io type is rcu or front-panel. This factory object will create the required product. The factory object has a dependency on the abstract user-io. This user-io will force to have the concrete class the following methods - Channel up, Channel down, Volume up, Volume down, Power Up/down and the number key ( which may not be in the front-panel). Thus front panel will not do anything on the method number key pressed.

The factory object will create the concrete class ( rcu or fp) and will store in the user-io type pointer.

The main class, will create a factory object, that can be singleton, and will have the related objects with it.

Can I say that the advantage here what I will gain is the following
a. The related classes are consolidated/organized together.
b. When I want to access the rcu or fp. I see them as only user-io, which is true by concept.
c. The FP will have the led or flash light functionality.So, while creating the fp, I need to create LED object also. A FP dependency on the LED,which I can hide from the user

Disadvantage -
1. Although frontpanel doesn't have number key pressed functionality. I will be adding the dummy method for frontpanel also.

答:
The Final products which you want to create are

1) Remote control Unit

2) Front Panel

3) Buttons on Setup box

So, I think the situation is not highly dynamic. (May be in future you may have to add one more type of new device.)

so, with Factory Method / Abstract factory we end up with parallel creator class hierarchy.
This approach of creating objects would unnecessarily add too many creator classes.

so, a little variation on factory method is "Static Factory method" which will make sure it creates required class object(s ) based on the need.

And as mentioned above, you may just need one "Virtual-Base" which defines General operations and the default behaviour. Derived class will override what is needed for it.


问:
How to create user defined conditional statements in c?
I have two stacks s1 and s2 with numbers stored in them.

I have a function(say comp) which compares the numerical values of s1 and s2.

I want to know if it is possible to modify the function so that I can use the conditional statements like:

```<code>If(s1>s2){statememts}
</code>```

The naive idea to convert the stacks to their numerical values and then comparing, wont work for me as the stacks contain large numbers(around 30 digits) and the default data type overflows.

答:
What you need for that is called operator overloading, which is not supported in C. See the question here:
https://stackoverflow.com/questions/3417413/operator-overloading-in-c

You could write it in C++ though ...


问:
Will destructing a large list overflow my stack?
Consider the following singly linked list implementation:

```<code>struct node {
    std::unique_ptr<node> next;
    ComplicatedDestructorClass data;
}
</code>```

Now, suppose I stop using some std::unique_ptr<node> head instance that then goes out of scope, causing its destructor to be called.

Will this blow my stack for sufficiently large lists? Is it fair to assume that the compiler will do a pretty complicated optimization (inline unique_ptr's destructor into node's, then use tail recursion), which gets much harder if I do the following (since the data destructor would obfuscate next's, making it hard for the compiler to notice the potential reordering and tail call opportunity):

```<code>struct node {
    std::shared_ptr<node> next;
    ComplicatedDestructorClass data;
}
</code>```

If data somehow has a pointer to its node then it might even be impossible for tail recursion (though of course we should strive to avoid such breaches of encapsulation).

In general, how is one supposed to destroy this list otherwise, then? We can't traverse through the list and delete the "current" node because shared pointer doesn't have a release! The only way is with a custom deleter, which is really smelly to me.

答:
To be honest I am not familiar with the smart pointer deallocation algorithm of any C++ compiler, but I can imagine a simple, non-recursive algorithm that does this.
Consider this:

You have a queue of smart pointers waiting for deallocation.

You have a function that takes the first pointer and deallocates it, and repeats this until the queue is empty.

If a smart pointer needs deallocation, it gets pushed into the queue and the above function gets called.

Hence there would be no chance for the stack to overflow, and it is much simpler that optimizing a recursive algorithm.

I am not sure if this fits into the "almost zero cost smart pointers" philosophy.

I would guess that what you described would not cause stack overflow, but you could try to construct a clever experiment to prove me wrong.

UPDATE

Well, this proves wrong what I wrote previously:

```<code>#include <iostream>
#include <memory>

using namespace std;

class Node;

Node *last;
long i;

class Node
{
public:
   unique_ptr<Node> next;
   ~Node()
   {
     last->next.reset(new Node);
     last = last->next.get();
     cout << i++ << endl;
   }
};

void ignite()
{
    Node n;
    n.next.reset(new Node);
    last = n.next.get();
}

int main()
{
    i = 0;
    ignite();
    return 0;
}
</code>```

This program eternally builds, and deconstructs a chain of nodes. It does cause stack overflow.

Body:
To be honest I am not familiar with the smart pointer deallocation algorithm of any C++ compiler, but I can imagine a simple, non-recursive algorithm that does this.
Consider this:

You have a queue of smart pointers waiting for deallocation.

You have a function that takes the first pointer and deallocates it, and repeats this until the queue is empty.

If a smart pointer needs deallocation, it gets pushed into the queue and the above function gets called.

Hence there would be no chance for the stack to overflow, and it is much simpler that optimizing a recursive algorithm.

I am not sure if this fits into the "almost zero cost smart pointers" philosophy.

I would guess that what you described would not cause stack overflow, but you could try to construct a clever experiment to prove me wrong.

UPDATE

Well, this proves wrong what I wrote previously:

#include <iostream>
#include <memory>

using namespace std;

class Node;

Node *last;
long i;

class Node
{
public:
   unique_ptr<Node> next;
   ~Node()
   {
     last->next.reset(new Node);
     last = last->next.get();
     cout << i++ << endl;
   }
};

void ignite()
{
    Node n;
    n.next.reset(new Node);
    last = n.next.get();
}

int main()
{
    i = 0;
    ignite();
    return 0;
}

This program eternally builds, and deconstructs a chain of nodes. It does cause stack overflow.


答:
Yes, this will eventually blow your stack, unless the compiler just happens to apply a tail call optimization to node's destructor and shared_ptr's destructor. The latter is extremely dependent on the standard library implementation. Microsoft's STL, for example, will never do that, because shared_ptr first decrements its pointee's reference count (possibly destroying the object) and then decrements its control block's reference count (the weak reference count). So the inner destructor is not a tail call. It's also a virtual call, which makes it even less likely that it will get optimized.

Typical lists get around that problem by not having one node own the next, but by having one container that owns all nodes, and uses a loop to delete everything in the destructor.

Title: Will destructing a large list overflow my stack?

Body:
Consider the following singly linked list implementation:

```<code>struct node {
    std::unique_ptr<node> next;
    ComplicatedDestructorClass data;
}
</code>```

Now, suppose I stop using some std::unique_ptr<node> head instance that then goes out of scope, causing its destructor to be called.

Will this blow my stack for sufficiently large lists? Is it fair to assume that the compiler will do a pretty complicated optimization (inline unique_ptr's destructor into node's, then use tail recursion), which gets much harder if I do the following (since the data destructor would obfuscate next's, making it hard for the compiler to notice the potential reordering and tail call opportunity):

```<code>struct node {
    std::shared_ptr<node> next;
    ComplicatedDestructorClass data;
}
</code>```

If data somehow has a pointer to its node then it might even be impossible for tail recursion (though of course we should strive to avoid such breaches of encapsulation).

In general, how is one supposed to destroy this list otherwise, then? We can't traverse through the list and delete the "current" node because shared pointer doesn't have a release! The only way is with a custom deleter, which is really smelly to me.


问:
Which languages are used today for low-level programming?
When I hear low-level programming, such as for drivers, embedded systems, operating systems, etc., I immediately think about C and perhaps C++. But mainly C.

But what other languages are also used for these kind of tasks? Today, I mean, not what has been used.

答:
Cython is one example. Not for embedded systems, but for drivers and other low level programming it's used more and more in the Python world as a replacement of C. You get both a compiled Python, but also low level access and type hints for speedups.

As a Python fanatic that's what I use, although admittedly very rarely and so far not in any serious context.