AV色综合久久天堂AV色综合在,精品久久久久中文字幕一区,亚洲综合伊人久久综合

散列3

Fri, 27 Nov 2009 09:14:00 GMT

散列�q�是最后一章了�Q�快毕业了，�q�几天赶快把论文写完�Q�到回家�q�不��C��个月�Q�答应张老师再去实验室把做的东西�ȝ��一下，其实打算在实验室再呆两个月，腊月底再回，惛_��的东西嘛�Q�我想研�I�一下opencv的内存管理机�Ӟ��l�合我买的那本Applied C++,��Z��推销一下这本书�Q�这本书很薄�Q�两癑֤��，介绍如何应用c++来解军_��发商业��Y件时所固有的问题，最难能可贵的是�Q�从头至��提供了一个图像处理框�Ӟ��对于惛_��数字囑փ�处理�Q�机器视觉方向深入探�IӞ��不是具体��法�Q�而是整个软�g架构�Q�有挺大的启发意义的(虽然�|�上评�h不是太好�Q�可能比较牛的�h看不上吧�Q�也有可能这本书比较偏重于数字图像领�?�Q�还惛_��的东西呢�Q�年前和�q�后几个月的旉��Bjarne Stroustrup的那本c++,Mark Allen Weiss的那本数据结构，Jon Kleinberg 的那本算法设计，后两本书是俺在图像室的图书角扑ֈ�的，非常的不错哦�Q�可惜毕业前��p��q�，正好督促我赶紧看�Q�在联合书城看到Richard Johnsonbaugh的Discrete Mathematics,竟然是第七版了，只能怪我资质太差看不懂knuth的那三本圣经�Q�只好咬着牙买下来先琢��琢��了��是打基��了，公司有项目做嵌入式��^��C��的编译器�Q�要是有旉��的话看看嵌入式操作系�l�和�~�译原理吧，很想写个�~�译器，�q�么多好书要看，有时候真不想回家�q�年了，嘿嘿�Q�说着玩的�Q�到时候家里肯定杀猪了�Q�不回去真是太可惜了�?br>
1.再散�?br> 其实��是前两��中有提到的rehash了，对于使用�q�x��探测的开攑֮�制散列法�Q�如果表的元素填得太满，那么操作的运行时间将开始消耗过长，且插入操作可能失败。这可能发生在有太多删除和插入�؜合的场合。此�Ӟ��一个解��x��法是建立另外一个大�U�两倍大的表(而且使用一个相关的新散列函�?�Q�扫描整个原始散列表�Q�计��每�?未删除的)元素的新散列值�ƈ��其插入到新表中。整个操作成为再散列(rehashing)。这昄��是一�U�非常昂�늚�操作�Q�其�q�行旉��为O(N),因�ؓ有N个元素要再散列而且表的大小�U��ؓ2N�Q�不�q�，因�ؓ不是�l�常发生�Q�所以实际效果�ƈ没有�q�么差。特别是�Q�在最后的再散列之前已�l�存在N/2�ơ插入，因此��d��到每个插入上的花费基本是一个常数开销。如果这�U�数据结构是�E�序的一部分�Q�那么其影响是不明显的。另一斚w��Q�如果再散列作�ؓ交互�pȝ��一部分�q�行�Q�那么其插入引�v再散列的用户��会感到速度减慢�?br> 再散列可以用�q�x��预测以多�U�方法实现。一�U�做法是只要表满一半就再散列。另一�U�极端的�Ҏ��是只有当插入��p�|时才再散列。第三种�Ҏ��即途中(middle-of-the-road)�{�略�Q�当表到达某一个装填因子时�q�行再散列。由于随着装填因子的增加，表的性能的确在下降，因此�Q�以好的截至点实现的�W�三�U�策略，可能是最好的�{�略�?br>

1//�Ҏ��散列表和分��链接散列表的再散列
2void rehash()
3{
4    vector<HashEntry> oldArray = array;
5    array.resize( nextPrime( 2* oldArray.size() ) );
6    for( int j = 0; j<array.size(); j++ )
7        array[j].info = EMPTY;
8    currentSize = 0;
9    for( int i = 0; i<oldArray.size(); i++ )
10        if( oldArray[i].info == ACTIVE )
11            insert( oldArray[i].element );
12}
13
14void rehash()
15{
16    vector<list<HashedObj> > oldLists = theLists;
17    theLists.resize( nextPrime( 2* theLists.size() ) );
18    for( int j = 0; j<theLists.size(); j++ )
19        theLists[j].clear();
20    currentSize = 0;
21    for( int i = 0; i<oldLists.size(); i++ )
22    {
23        list<HashedObj>::iterator itr = OldLists[i].begin();
24        while ( itr != oldLists[i].end() )
25            insert( *itr++ );
26    }
27}

2.标准库中的散列表
    标准库中不包括set和map的散列表实现。但是，许多的编译器提供��h��与set和map�cȝ��同的成员函数的hash_set和hash_map.
    要��用hash_set和hash_map�Q�就必须有相应的包含指��o�Q�而且�Q�可能也需要相应的命名�I�间。这两者都是和�~�译器相关的。接下来�q�必��L��供相应的�c�d��参数来说�?br>hash_set和hash_map。对于hash_map�Q�这些类型参数包括键的类型，值的�c�d��Q�散列函�?�q�回无符��h��?和一个相�{�性操作符。遗憄��是，至于键和值的�c�d��参数如何
表示�q�是�~�译器相关的�?br>    下一�ơc++的较大的修订��不可避免地包括�q�些hash_set和hash_map中的一个�?br>
3.可扩散列
    最后讨论数据量太大以至于装不进��d��的情况，此时主要考虑的是��索数据所需的磁盘存取次数。假讑֜��L��时刻都有N个记录要存储�Q�N的值随旉��而变化。此外，最多可把M个记录放入一个磁盘区块，设M=4,如果使用探测散列或分��链接散列，那么主要的问题在于，即��是理惛_��布的散列表，在一�ơ查找操作中�Q�冲�H�也可能引�v对多个区块的讉K��。不仅如此，当表变得�q�慢的时候，必须执行代�h巨大的再散列�q�一步，它需要O(N)的磁盘访问�?br>    一�U�聪明的选择成�ؓ可扩散列(extendible hashing),它允许用两次��盘讉K��执行一�ơ查找。插入操作也需要很��的��盘讉K��.
   Extendible hashing from Wikipedia
   Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

This is a more simplistic example from Fagin et al. (1979).

Assume that the hash function $h (k)$ returns a binary number. The first i bits of each string will be used as indices to figure out where they will go in the "directory" (hash table). Additionally, i is the smallest number such that the first i bits of all keys are different.

Keys to be used:

$h (k 1)$ = 100100
$h (k 2)$ = 010110
$h (k 3)$ = 110110

Let's assume that for this particular example, the bucket size is 1. The first two keys to be inserted, k₁ and k₂, can be distinguished by the most significant bit, and would be inserted into the table as follows:

 directory
---------
|    0    |-----------> Bucket A (contains k2)
|---------|
|    1    |-----------> Bucket B (contains k1)
---------

Now, if k₃ were to be hashed to the table, it wouldn't be enough to distinguish all three keys by one bit (because k₃ and k₁ have 1 as their leftmost bit. Also, because the bucket size is one, the table would overflow. Because comparing the first two most significant bits would give each key a unique location, the directory size is doubled as follows:

  directory
----------
|    00    |-----\
|----------|      ----------> Bucket A (contains k2)
|    01    |-----/
|----------|
|    10    |-----------> Bucket B (contains k1)
|----------|
|    11    |-----------> Bucket C (contains k3)
----------

And so now k₁ and k₃ have a unique location, being distinguished by the first two leftmost bits. Because k₂ is in the top half of the table, both 00 and 01 point to it because there is no other key to compare to that begins with a 0.

4.��结
散列表可以用来以常数�q�_��旉��实现insert和contains操作。当使用散列表时�Q�注意诸如装填因子这��L��l�节是特别重要的�Q�否则时间界��不再有效。当键不是短字符串或整数�Ӟ��仔细选择散列函数也是很重要的�?br> 对于分离链接散列法，虽然装弹因子不大时性能�q�不明显降低�Q�但装填因子�q�是应该接近�?�Q�对于探��散列，除非完全不可避免�Q�否则装填因子不应该��过0.5�Q�如果��用线性探��，那么性能随着装填因子接近�?而急速下降。再散列�q�算可以通过使表增长(或收�~?来实玎ͼ��q�样可以保持合理的装填因子。对于空间紧�~��ƈ且不可能声明巨大散列表的情况�Q�这是很重要的�?br> 二叉查找树也可以用来实现insert和contains操作。虽然��^均时间界为O(logN)�Q�但是二叉查找树也支持那些需要排序的例程�Q�从而功能更强大�Q��用散列表不可能找出最��元素。除非准��知道一个字�W�串�Q�否则散列表也不可能有效地查扑֮�。二叉查找树可以�q�速找��C��定范围内的所有项�Q�散列表却做不到。不仅如此，因�ؓ查找树不需要乘法和除法�Q�O(logN)�q�个旉��界也不必比O(1)大那么多�?br> 另一斚w��Q�散列的最坏情形一般来自于实现错误�Q�而有序的输入却可能��二叉树运行得很差。��^衡查找树实现的代��L��当高。因此，如果不需要排序的信息或者不��定输入是否已经排序�Q�那么就应该选择散列�q�种数据�l�构�?br> 散列的应用很�qѝ��编译器使用散列表跟�t�源代码中声明的变量�Q�这�U�数据结构叫做符可��(symbol table)。散列表时这�U�问题的理想选择。标识符一般都不长�Q�因此散列函数能够迅速完成运��。此外，按字母顺序排序变量通常也是不必要的�?br> 散列表适用于�Q何其节点有实名而不是数字名的图论问题。这里，当输入被��d��的时候，定点则按照它们出现的��序�?开始指定�ؓ一些整数。再有，输入很可能有一�l�按字母��序排列的项。例如，��点可以是计��机。此�Ӟ��如果一个特定的计算中心把它的计��机列表成ibm1,ibm2,ibm3...那么�Q�若使用查找树则在效率方面很可能会有戏剧性的�l�果�?br> 散列表的�W�三�U�常见的用途实在�ؓ游戏�~�制的程序中。当�E�序搜烦游戏的不同的�q�动路径�Ӟ��它通过计算��Z��位置的散列函数而跟�t�一些已知的位置(�q�把对于该位�|�的�U�d��存储��h��)。如果同��L��位置再次出现�Q�程序通常通过��单的�U�d��变换来避免昂�늚�重复计算。游戏程序的�q�种一般特点叫做置换表(transposition table�Q?
散列的另一个用途是在线拼写��查程序。如果拼写检查程序的主要功能是检查拼写错�?而非�U�正错误),那么可以预先��整个词典进行散列，�q�样��可以在常数旉��内检查单词拼写。散列表很适合�q�项工作�Q�因��Z��字母��序排列单词�q�不重要�Q�而以它们在文件中出现的顺序显�C�错误拼写当然也是可以接受的�?/span>

��罗�|?/a> 2009-11-27 17:14 发表评论

老外谈future of c++

Thu, 26 Nov 2009 16:23:00 GMT

又去Bartosz的c++ in action论坛上�{了�{�Q�看��C��个老外问Bartosz哥哥future of c++的帖�?论坛比较��h��Q�没有c++er和javaer们的互相炮蘪�Q�Bartosz有意思的是没忘记向各位推销他的D语言。。�?br>

helmi:

Hi, I just found this very useful site and I have read almost all of tutorial, guide, articles.

I just ask everybody opinion on the future of C/C++ because a lot of other programming language out there now days. What do you think since more applications develop as on web base platform? This is just my observation in my country. I really like coding in C++ because I can feel I'm doing low level programming. I do have write game using directX as a hobby but to sustain, I have need to write applications using php, asp .net and jsp.

ps: Sorry for my bad English.

Bartosz�Q?/strong>
I see programming tasks as a pyramid. The base of the pyramid is formed by small tasks that don't require sophisticated languages or tools. That's where most of the programming is done. The top of the pyramid are tough tasks that just can't be done using Java or C#. Right now the language at the top is C++. There aren't very many complex tasks, so the top of the pyramid is rather narrow, but then the number of seasoned C++ programmers is also relatively small. In the United States, C++ programmers are in high demand (and are very well paid).

Will C++ keep its top position? I don't know. There are very many aspects of C++ that are very unsatisfactory. I am now involved in the development of the D language (http://digitalmars.com/d/), which has a chance of replacing C++.

helmi:

"the number of seasoned C++ programmers is also relatively small. In the United States, C++ programmers are in high demand (and are very well paid)."

Really? I should go working in the United States

I have read of about the D language in a game forum. It's has a lot of features and so powerful but still need improvement, good IDE etc.

Bartosz�Q?/strong>

QUOTE (helmi @ Feb 1 2007, 05:30 PM)

I have read of about the D language in a game forum. It's has a lot of features and so powerful but still need improvement, good IDE etc.

That's right. It needs an IDE, tools, and libraries. But it has a good chance of acqiring them quickly.

peter:

QUOTE (Bartosz @ Feb 2 2007, 04:32 AM)

That's right. It needs an IDE, tools, and libraries. But it has a good chance of acqiring them quickly.

It would be great if there were a Visual Studio package for D .

Unfortunately after trying to figure out how to do that by
browsing the Visual Studio SKD documentation and samples
for the last two days I finally gave up .

There are two frameworks that are supposed to help
with the package development. One is written in C#
and the second is in C++ (depends heavily on Microsoft's ATL).
These are pretty heavy beasts and doesn't really
help if the developer doesn't get The Big Picture
(as I failed to get).

So, I tried to implement a package from scratch.

So far I get the IDE to show a new project type
and to call my implementation of the IVsProjectFactory
interface. When the IDE calls the
IVsProjectFactory::CreateProject I copy
the project template files into the new project
directory. Then I create an object implementating
the IVsProject3 and IVsHierarchy interfaces and
return it back to the IDE.
This is where I am stuck. Although the IDE then
calls some methods on the IVsProject3 and
IVsHierarchy interfaces, querying and setting
some properties. The IDE doesn't show the
new project node in the solution explorer.
There is only the topmost solution node
"Solution 'Project1' (1 Project)", nothing more.

And as I said before I was not able to figure out
what am I supposed to do after the project is created...

~Peter

Bartosz�Q?/strong>

The best resource in this kind of projects are Microsoft forums. Here's a thread about adding language services to VS
adding language services to VS , and here's a more comprehensive list . Without these forums I would have never been able to embed the internet browser control in Code Co-op.

Another-- maybe even more attractive--option is to write an extension to Eclipse. There's been some discussion about it in the D forum, but it doesn't look like there are many volunteers.

peter:

Speaking about the D Programming Language.

How does it handle source file dependencies?

If I have two files File1.d and File2.d
and File2.d imports File1, then when
File1.d changes both files must be
recompiled.

Is my assumption correct?

~Peter

Bartosz:

This is a functionality of "make", not the compiler. But if you mean: Should both files be recompiled?; the answer is, yes.

Note also that you can generate D interface files, .di, which speed up the import process. These too have to be recompiled whenever their correspondig D file changes.

peter:

(Maybe you could add a new forum section about "D Programming" :-)

I wonder how one implements resource ownership transfer semantic in D?

~Peter

Bartosz:

QUOTE (peter @ Feb 15 2007, 07:34 AM)

(Maybe you could add a new forum section about "D Programming" :-)

I will do exactly that!

helmi:

It is a good idea.

James:

I hope none of you mind me butting in for just a second.

I am currently a student in high school and I am interested in computer science and programming. I am fluent (on an intermediate level) in PHP (HTML, XML, and some minor AJAX/JS included). I would say I have a decent understanding of general coding practice/syntax/what have you, so I am certainly not starting from scratch.

In terms of D, C++, C#, Java, etc., where should I be focusing my efforts? I know there really isn't a straight forward answer, but maybe some of you could offer your opinion. I'm not necessarily looking for something thats going to land me the biggest paycheck (although I would be interested in what you have to say on the subject), but more something that will give me a good background for future endeavors, whether or not it be a new language.

I'm not sure if I can really go wrong, but I am just trying to find something that might suit me the best. I am not setting out to make anything in particular, like games or stuff along those lines. As said, I am just interest in furthering my understanding and setting myself up for down the road. Any tips you can offer me would be great.

Thanks

James

Bartosz:

QUOTE (James @ Feb 20 2007, 02:02 PM)

In terms of D, C++, C#, Java, etc., where should I be focusing my efforts?
These languages have very similar structure, so my suggestion would be to learn them all. In order of difficulty, from easiest to hardest:
- Java
- C#
- D
- C++
Specializing in one single language not only pidgenholes you as a developer, but also prevents you from learning different programming styles.
James:

Thanks. I appreciate the reply.

Dave:

I've programming in Java, C#, C++ and many other languages over many years.

I've never seen any commercial demand for D so that may well be a stumbling point. I would look very closely at what happened to Borland/CodeGear. Of course alot of unix based open source languages have done well so maybe i'm wrong.

Bjarne is working on his next version of C++ called C++ 0x, I doubt even this will get traction in many places.

Assembler, C and C++ were general purpose system level languages, things have moved on now, sure they are still valid for development of the OS, drivers, performance and memory footprint critical software, but they do not support many of the higher level primitives business software and web developers want.

Most programmers in the world however don't work on the large volume projects where the increased development costs can be amortised. They work on custom in house solutions to business problems, this is why we have Java and C#, they are the modern equivalent of Smalltalk that is now feasible due to vast hardware resources. These projects generally last only a few years before a rewrite making developer cost a large factor, and hardware cost fairly insignificant.

I would therefore strongly advise most people to learn at least one high level language to go with their lower level languages in order to have a successful career. Its unfortunate alot of the old skills are being lost in assembler, compiler design etc. I would still certainly reccomend most new students learning C# or Java over C/C++ or D as their first language.

Eclipse is an excellent open source IDE, It already supports multiple languages, and runs on multiple OS's it might be a better bet for D than Visual Studio.

ivec:

QUOTE (Dave @ Aug 23 2007, 12:25 PM)

Bjarne is working on his next version of C++ called C++ 0x, I doubt even this will get traction in many places.

This is just so inaccurate that I have to clarify:
This is not about "Bjarne working on his next version of his language".
It is the ISO C++ standard committee working on the next revision of the standard C++ language. This is a collaborative and active process, as can be seen at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/ .

When the standard is adopted (expected in a couple of years), you can be certain that all vendors of C++ compilers will be implementing the features introduced in the new standard. I am very confident that the new standard will have no problem getting traction wherever C++ remains relevant.

--------------------

http://ivan.vecerina.com

Bartosz:

Yes, a lot of bright people work on the development of C++, not only in the Standards Committee; and I expect C++ 0x to introduce a lot of great features.

There are however some aspects of language development that are not reachable from the current state of C++, because of backwards compatibility. That's where D will shine. Version 2.0 of D is expected about the same time as C++ 0x-- meaning, before 2010. (The 0x stands for 200x--C++ is cutting it real close!).

As an example, D will unify templates and function templates--In D a function is just a fully specialized template.

hansgostajonsson:

Hello! As a hobby programmer I am hardly qualified to write here but: When I studied programming at university in 1987 I learnt pascal and loved it. It was said to be the future, but "for old times sake" we were also required to learn cobol and fortran - 2 languages then thought to be barely breathing. They seem , however, still to be hanging around, pascal is still in swing as Delphi but it was not so long after I learnt it said to be decrepit and I had to move on to c and then c++ if I wanted to move with the times. Then Java was the swinging language and so on to c#. Now D looms high on the horizon. It may seem a naive question but why can't d be implemented as a development of c++ - to an amateur it seems a look alike. hans jönsson

Bartosz:

If you look at the development of C++ over the years you'll notice that virtually every feature that's been added to the language stays with it, whether it made sense or not. If you imagine C as a fast but flimsy and dangerous ship, C++ grew layers and layers of barnacles over it, in the hope to strengthening it. Instead C++ has kept all the weaknesses of C at its core; plus it made if very difficult not only to master, but even to start learning.

The direction of D that I'm advocating is to make it as easy and safe for beginners as Java or C#. You should be able to use D productively without the need to understand pointers or memory management (D is garbage-collected). D has built in (and very efficient) arrays and strings. Classes are treated pretty much like in Java.

But unlike Java, D also offers all the sophisticated features of C++, except that they were desingned into the language from the start. Instead of layers of barnacles you have some well designed solid language architecture.

peter:

Personally, I don't believe that Yet Another Programming Language Based on C/C++, Java, etc. will make our coding and code maintaining life any easier. Programming languages evolved over 50 years yet I think the most radical step to writing more correct and more maintainable software was that from FORTRAN to ALGOL. From that point on any new language (from the ALGOL family) brings IMHO only very marginal improvements wrt. code maintainability and I don't think this will change in the future. Also after that 50 year of programming evolution and experience our best programming tool is still a simple text editor. I don't think this is right.

Presently, I'm slowly turning my attention to other programming paradigms. From them I see the Data Flow and Multi Agent paradigms most promising partly due to their great potential to exploit the future many-core processors. Also they lend themselves more easily to "diagrammatic" and/or visual programming than present day mainstream programming languages.

Just my �?.02

~Peter

P.S. I sometimes browse through the digitalmars.D newsserver and, frankly, based on most posts there the very LAST thing I'd say about the D programming language is: "well designed solid language architecture".

Also, I looked at the sources for the D compiler and the first immediate thought was: What programming language can design a person with such coding practices... I mean no offense to Walter Bright (I really admire his persistence and devotion to his creation), but those were just my feelings.

hansgostajonsson:

Thanks for replies. A few musings. A new language, like reorganizations, give new hope an generally we learn something in the process. I am a newly retired psychologist with old studies in computer science. Psychology differs from other sciences - it is one in many of it's fields - in that it has been founded a couple of times ( Gestalt psychology, functionalism, behaviourism) - not once like most other sciences. It seems to be the same for language development in computer science and you long for something like the explanation of dna when genetics became molecular biology and never has looked back again. Parhaps a futile dream. It seems that d is based on practical considerations rather than theoretical progress and therefore will be superseeded by the next language but not killed off. I think one problem is that new languages are not good enough to kill once and for all older languages. We will have a lot of not so good but good enough ones hanging around - the same in psychology. Just a few musings. Thanks for a very interesting site. greetings hans jönsson

Bartosz:

QUOTE (peter @ Mar 4 2008, 05:22 AM)

Personally, I don't believe that Yet Another Programming Language Based on C/C++, Java, etc. will make our coding and code maintaining life any easier. Programming languages evolved over 50 years yet I think the most radical step to writing more correct and more maintainable software was that from FORTRAN to ALGOL. From that point on any new language (from the ALGOL family) brings IMHO only very marginal improvements wrt. code maintainability and I don't think this will change in the future.

A lot happend since ALGOL. Probably the biggest revolution was the introduction of the object oriented paradigm. OO programs are a lot more maintainable. In other areas progress was more quantitative than qualitative, but the accumulation of changes can make a lot of difference. Garbage collection, for instance, has entered the mainstream. So did functional programming techniques. There was also a shift of emphasis towards safe programming. Not to mention the latest revolution--multicore. Java bit the bullet by defining a memory model for parallel programming. C++ is working on it too.

QUOTE

Also after that 50 year of programming evolution and experience our best programming tool is still a simple text editor. I don't think this is right.
No, it's not right. Personally, I use Visual Studio in my C++ development. I also used Eclipse for Java. C++ has some of the worst development tools because it's such a hard language to parse. By the way, there is a D plugin for Eclipse. I didn't use it because it doesn't support D 2.0 yet.

QUOTE

Presently, I'm slowly turning my attention to other programming paradigms. From them I see the Data Flow and Multi Agent paradigms most promising partly due to their great potential to exploit the future many-core processors. Also they lend themselves more easily to "diagrammatic" and/or visual programming than present day mainstream programming languages.
These are all cool paradigms, but they are still far from the mainstream. My current interest is in Software Transactional Memory as the new paradigm for multicore programming.

QUOTE

P.S. I sometimes browse through the digitalmars.D newsserver and, frankly, based on most posts there the very LAST thing I'd say about the D programming language is: "well designed solid language architecture".
Point taken. Version 2.0 is still in flux. It might look like there is a lot of random experimenting, but there is solid theory behind most of it. In fact I'm pushing for updating the D manifesto to better explain the goals of the language. There is also a big difference between version 1.0 and 2.0. Version 1.0 was more of a "better C++". 2.0 is way beyond that.

QUOTE

Also, I looked at the sources for the D compiler and the first immediate thought was: What programming language can design a person with such coding practices... I mean no offense to Walter Bright (I really admire his persistence and devotion to his creation), but those were just my feelings.

Touche! What can I say, I'm not fond of Walter's programming style either .

Bartosz:

QUOTE (hansgostajonsson @ Mar 4 2008, 12:51 PM)

It seems that d is based on practical considerations rather than theoretical progress

Practical considerations make or break a language. There are some theoretically beautiful languages that nobody uses outside of the academia because they are not practical.

But there's also a lot of theoretical progress in computer science that is being incorporated into D.

Hossein:

QUOTE (Bartosz @ Mar 4 2008, 11:10 PM)

But there's also a lot of theoretical progress in computer science that is being incorporated into D.

Wow! This is what amused me in the first place in fact! OK, it seems that I can deny my extreme laziness here, and ask for this from you (Bartosz): Could you please give a list of all these nice features of D which attract us -- the snubish [] people of Theoretical Computer Science of academia?

(And, BTW, like I mentioned in some other posting: People of academia wouldn't really like it that they don't publish proceedings in their D conferences...)

Cheers,
--Hossein

Bartosz:

We are trying to incorporate the latest PL trends in D, sometimes even before they mature .

One major area is safe programming. There's been a lot of research into proving soundness of various languages using operational semantics. It culminated in the soundness proof for Featherweight (Generic) Java. Although it's not a goal of D to be a sound language (we do want pointers after all), we are defining a sound subset of D. In particular, we have a program that can translate Java programs into this subset. We will have one-to-one correspondence between Java semantics and the semantics of a subset of D (which is equivalent to having denotational semantics for the D subset).

We are planning on extending the safe D subset with other sound features, such as discriminated unions and elements of functional programming. D already supports anonymous functions and closures.

The other major area is concurrent programming. Again, Java leads the crowd with its memory model. D's memory model will most likely resemble that of C++ (still in the form of a proposal). The difference between the Java model and the C++ model is that Java gives some guarantees even for programs with race conditions-- C++ doesn't. So a racy program in C++ may exhibit undefined behavior. On the other hand Java has a virtual machine that may enforce a lot more during runtime that can be accomplished in a compiled language.

How can we support safe concurrency in the presence of races--or eliminate the races altogether? The idea is to build software transactional memory into D. Even though STM might not offer the best performance, it is much safer (and easier) than lock-based programming. Especially if we can build support for transactions into the type system, as has been done for Concurrent Haskell.

markm:

IDE for D use CodeBlocks, version 8.02 supports D.

http://www.codeblocks.org/

��罗�|?/a> 2009-11-27 00:23 发表评论

散列2

Thu, 26 Nov 2009 12:20:00 GMT

3 不��用链表的散列�?br>    分离链接散列��法的缺�Ҏ��使用一些链表。由于给新单元分配地址需要时��_��因此�q�就��D��法的速度有些�~�慢�Q�同时算法实际上�q�要求第二种数据�l�构的实现。解军_��H�的另一个方法是当冲�H�发生时��尝试选择另一个单元，直到扑ֈ��I�的单元。更正式圎ͼ�单元h_i(x)=(hash(x)+f(i))mod TableSize,且f(0)=0.函数f是冲�H�解军_��数。因为所有的数据都要�|�入表内�Q�所以��用这个方案所需要的表要比分��链接散列需要的表大。一般说来，对不使用分离链接法的散列表来��_��其装填因子应该低�?#955;=0.5。我们称�q�样的表为探��散列表(probing hash tables)�?br>    (1)当f是i的线性函数时�Q��ؓ�U�性探��，一般情况下f(i)=i�Q�线性探��容易在占据的单元�Ş成一些区块，其结果成��Z��ơ聚�?primary clustering)�?br>    (2)�q�x��探测是消除线性探��中一�ơ聚集问题的冲突解决�Ҏ��。��^�Ҏ��就是冲�H�函��Cؓ二次函数的探��方法。流行的选择是f(i)=i².
               定理�Q�如果��用��^�Ҏ��，且表的大��是素数�Q�那么当表至��有一半是�I�的时候，总能够插入一个新的元素�?br>        如果哪怕表有比一半多一个的位置被填满，那么插入都有可能��p�|(虽然�q�种可能性极��?。另外，表的大小是素��C��非常重要。如果表的大��不是素敎ͼ�则备选单�?br>       的个数可能会锐减。例如，若表的大��是16�Q�那么备选单元只能在距散列�?�Q?�?�q�处�?br>        在探��散列表中标准的删除操作不能执行�Q�因为相应的单元可能已经引�v�q�冲�H�，元素�l�过它存储在别处。因此，探测散列表需要懒惰删除�?/span>
        实现探测散列表所需要的�c�L��口在下图中给出。这里不使用链表数组�Q�而是使用散列表项单元数组。嵌套的�c�HashEntry存储在info成员中一个项的状态，�q�个状态可
       以是ACTIVE,EMPTY或DELETED�?br>


1//使用探测�{�略的散列表的类接口�Q�包括嵌套的HashEntry
2  �c?br> 3template <typename HashedObj>
4class HashTable
5{
6public:
7    explicit HashTable( int size = 101 );
8
9    bool contains( const HashedObj &x ) const;
10
11    void makeEmpty();
12    bool insert( const HashedObj &x );
13    bool remove( const HashedObj &x );
14
15    emum EntryType (ACTIVE,EMPTY,DELETED );
16
17private:
18    struct HashEntry
19    {
20        HashedObj element;
21        EntryType info;
22        HashEntry( const HashedObj & e = HashedObj(), EntryType i = EMPTY ) : element(e), info(i) { }
23    };
24
25    vector<HashEntry> array;
26    int currentSize;
27
28    bool isActive( int currentPos ) const;
29    int findPos( const HashedObj &x ) const;
30    void rehash();
31    int myhash( const HashedObj &x ) const;
32};

1//初始化��^�Ҏ��散列表的例�E?/span>
2explicit HashTable( int size = 101 ) : array(nextPrime( size ) )
3{ makeEmpty(); }
4
5void makeEmpty()
6{
7    currentSize = 0;
8    for( int i = 0; i<array.size(); i++ )
9        array[i].info = EMPTY;
10}

1//使用�q�x��探测�q�行散列的contains例程
2bool contains( const HashedObj &x ) const
3{
4    return isActive( findPos(x) ); }
5
6int findPos( const HashedObj &x ) const
7{
8    int offset = 1;
9    int currentPos = myhash(x);
10
11    //下面是一个小��的trick
12    while ( array[ currentPos ].info != EMPTY && array[ currentPos ].element != x )
13    {
14        currentPos += offset;
15        offset += 2;
16        if( currentPos >= array.size() )
17        currentPos -= array.size();
18    }
19
20    return currentPos;
21}
22
23bool isActive( int currentPos ) const
24{
25    return array[ currentPos ].info == ACTIVE; }

1//使用�q�x��探测的散列表的insert和remove例程
2bool insert ( const HashedObj &x )
3{
4    int currentPos = findPos( x );
5    if ( isActive ( currentPos ) )
6        return false;
7
8    array[ currentPos ] = hashEntry( x, ACTIVE );
9    if( ++currentSize > array.size() / 2 )
10        rehash();
11
12    return true;
13}
14
15bool remove( const HashedObj &x )
16{
17    int currentPos = findPos(x);
18    if ( !isActive( currentPos ) )
19        return false;
20
21    array[ currentPos ].info = DELETED;//传说中的懒惰删除
22    return true;
23}

  (3)最后一个冲�H�解��x��法是双散�?double hashing)。对于双散列�Q�一�U�流行的选择是f(i)=i*hash₂(x)。这个公式是��_��第二个散列函数应用到x�q�在距离hash₂(x),2hash₂(x),
      ...�{�处探测。hash₂(x)选择不好��会非常�p�糕�?br>
.

��罗�|?/a> 2009-11-26 20:20 发表评论

数据�l�构-散列1

Wed, 25 Nov 2009 14:22:00 GMT

    最�q�在看Bartosz Milewski的C++ In Action Industrial-Strength Programming Techniques�Q�这本书很不错，它不是语�a�基础教程�Q�全书主要介�l�了许多工业强度的编�E�技术，如清理，隐藏实现�l�节�Q�资源管理，�׃�n�Q�资源管理，使用标准模板库，重蝲�q�算�W�等技术。这是Bartosz Milewski的简�?Bartosz Milewski�Q�C++ In Action 的作者。是Reliable Software公司的总裁�Q�Reliable Software公司是一家�ؓ�E�序员制造高质量开发工��L��公司。在�q�去几年��_��Bartosz Milewski在多家知名杂志发表了大量技术文章。在微��Y工程工作�?�q�期��_��他担任Windows2000中Content Index�l��g的开发主��，他曾�l�在波兰的Wroclaw大学讲授C++�~�程评��Q�而且他获得了Wroclaw大学的理论物理学博士学位�?/span> �q�是他�ؓ�q�本书管理的blog:http://www.relisoft.com/forums/index.php?s=ee4c0dc7cafef9f08c7c18a6e449b424&showforum=3�Q�售后服务还不错�Q�呵呵，以我目前的水�q�看��h��q�挺累的�Q�我��x��好把C++ Primer和effective c++,more effective c++看完再看�q�本书会比较好，不过��着头皮看也有好处，��像有时候武侠小说里用非常规�Ҏ��提高修�ؓ有时候也能�v到意想不到的效果。言归正传，在这本书中多�ơ用到哈希表�Q�很多地方不明白�Q�查了书整理一下�?br>
    散列�?hash table)的实现常�U�Cؓ散列(hashing),散列是一�U�用于以常数�q�_��旉��执行插入�Q�删除和查找的技术。但是，那些需要元素间��M��排序信息的树操作不会得到有效的支持。因此诸如findMin,findMax以及在线性时间内按顺序打印整个表的操作都是散列所不支持的�?br>    我们把表的大��记作TableSize,我们把每个键映射��C��0到TableSize-1�q�个范围中的某个敎ͼ��q�且��其攑ֈ�适当的单元中。这个映��就�U�Cؓ散列函数(hash function),理想情况下它应该�q�算��单�ƈ且应该保证�Q何两个不同的键映��到不同的单元。不�q�，�q�是不可能的。因此我们寻找一个散列函敎ͼ�该函数要在单元之间均匀分配键。这��是散列的基本思想�Q�剩下的问题则是要选择一个函敎ͼ�军_��当两个键散列到同一个值的时�?�U�Cؓ(collision))应该做什么以及如何确定散列表的大��?br>
1.散列函数
    如果输入的键是整敎ͼ�一般合理的�Ҏ��是直接�q�回"Key mod Tablesize",但Key��h��某些不理想的性质�Q�比如若表的大小�?0而键的各位都�?。则此时上述标准的散列函数就不是一个好的选择�Q�好的办法通常是保证表的大��是素数�Q�当输入的键是随机整数时�Q�散列函��C��仅运��简单而且键的分配也很均匀�?br>    通常�Q�键是字�W�串�Q�在�q�种情�Ş下，散列函数需要仔�l�选择�?br>    一�U�选择�Ҏ��是把字符串中字符的ASCII码值加��h��Q�下面的例程实现了这�U�策略�?br>

1int hash( const string &key, int tableSize )
2{
3    int hashVal = 0;
4    for( int i=0; i<key.length(); i++ )
5        hashVal += key[i];
6    return hashVal % tableSize;
7}

    上述散列函数实现��h��单而且能够很快地算出答案。不�q�如果表很大�Q�则函数��׃��会很好地分配键。例如，设TableSize=10007(10007是素�?�Q��ƈ设所有的键至�?个字�W�长�Q�由于ASCII字符的值最多是127�Q�因此散列函数只能在0-1016之间取��|��昄��q�不是一�U�均匀的分配�?br>    另一个散列函数如下表�C�，�q�个散列函数假设Key臛_��三个字符。�?7表示英文字母表的字母个数外加一个空��|��?29�?7×27�Q�该函数只考察前三个字�W�，但是如果它们是随机的�Q�而表的大��还�?0007�Q�那么我们就会得��C��个合理的均衡分布。可是，英文不是随机的。虽�?个字�W�（忽略�I�格�Q�有26×26×26=17576�U�可能的�l�合�Q�但查验词汇量��够大的联��典却揭示出，3个字母的不同�l�合数实际上只有2851。即使这些组合没有冲�H�，也不�q�只有表�?8%被真正散列到。因此，虽然很容易计��，但是当散列表��_��大的时候这个函数还是不合适的�?br>

1int hash( const string &key, int tableSize )
2{
3    return (key[0]+27*key[1]+729*key[2]) % tableSize
4}

    下面的例�E�列��Z��W?�U�尝试。这个散列函数涉及键中的所有字�W�，�q�且一般可以分布得很好�Q�程序根据Horner法则计算一�?7的多��式函数。这个散列函数利用了允许溢出�q�个事实。这可能会引�q�负敎ͼ�因此在末��有附加的测试，�q�个散列函数��p��的分布而言未必是最好的�Q�但是确实具有极其简单的优点而且速度也很快。如果键特别长，那么该散列函数计��v来将会花费过多的旉��。在�q�种情况下通常做法是不使用所有的字符。此旉��的长度和性质��媄响选择。例如，键可能是完整的街道地址�Q�散列函数可以包括街道地址的几个字�W�，或许也包括城市名和邮政编码的几个字符。有些程序设计�h员通过只��用奇��C��|�上的字�W�来实现他们的散列函敎ͼ��q�里有这么一层想法：用计��散列函数节省下的时间来补偿由此产生的对均匀分布的函数的��d��q�扰�?br>

1int hash( const string &key, int tableSize )
2{
3    int hashVal = 0;
4    for(int i=0;i<key.length();i++)
5        hashVal = 37 * hashVal + key[i];
6    hashVal %= tableSize;
7    if( hashVal <0 )
8        hashVal += tableSize;
9    return hashVal;
10}

    剩下的主要编�E�细节是解决冲突。如果当一个元素在插入时与一个已�l�插入的元素散列到相同的��|��那么��׃�生一个冲�H�，�q�个冲突需要消除�?br>

2.分离链接�?br>    解决冲突的第一�U�方法通常�U�Cؓ分离链接�?separate chaining),其做法是��散列到同一个值的所有元素保留到一个链表中�Q�可以��用标准库中表的实现方法。如果空间很紧，则更可取的方法是避免使用它们(因�ؓ�q�些表是双向链表�Q�浪费空�?,为执行search,我们使用散列函数来确定究竟该遍历那个链表�Q�然后查扄��应的表。�ؓ执行insert�Q�我们检查相应的表来��定是否该元素已�l�在表中�?如果要插入重复元�Q�那么通常要留��Z��个额外的数据成员�Q�当出现匚w��事�g时这个数据成员增1),如果�q�个元素是个新的元素�Q�那么它��被插入到表的前端，�q�不仅因为方便，而且�q�因为最后插入的元素最有可能不久再�ơ被讉K��Q�实现分��链接法所需要的�c�L��构在下面的例�E�中�l�出。散列表�l�构存储一个链表数�l�，�q�个数组在构造函��C��指定�?br>

1//分离链接散列表的�c�L��?/span>
2template <typename HashedObj>
3 class HashTable
4 {
5public:
6    explicit HashTable( int size = 101 );
7
8    bool contains( const HashedObj &x ) const;
9
10   void makeEmpty();
11   void insert( const HashedObj x);
12   void remove( const HashedObj x);
13
14 private:
15    vector<list<HashedObj> > theLists;// >>是c++的一个运��符�Q�而且�?gt;长，因此两个>之间需要一个空�?br>16    int currentSize;
17
18    void rehash()
19    int myhash( const HashedObj &x ) const;
20};
21
22int hash( const string &key );
23int hash( int key );
24
25

    �q�里不��用那些将对象和类的大��作为参数的散列函数�Q�而是使用那些仅以对象为参数的散列函数�Q��ƈ且返回int。散列表�c�L��一个私有的成员函数myhash,�q�个函数��结果分配到一个合适的数组索引中�?/p>
1int myhash( const HashedObj &x ) const
2{
3    int hashVal = hash(x);
4    hashVal %=theLists.size();
5    if( hashVal < 0)
6        hashVal += theLists.size();
7    return hashVal;
8}
9
10

     下面的例�E�中列出了一个可以存储在一般散列表中的Employee�c�，该类使用name成员作�ؓ键，Employee�c�通过提供相等性操作符和一个散列函数来实现HashedObj的需求�?br>

1class Employee
2{
3public:
4    const string & getname() const
5        { return name; }
6    bool operator==( const Employee &rhs )  const
7        { return getName() == rhs.getName(); }
8    bool operator!=( const Employee & rhs } const
9        { return !(*this == rhs); }
10
11private:
12    string name;
13    double salary;
14    int seniority;
15};
16
17int hash( const Employ &item )
18{
19    return hash( item.getName() );
20}

    实现makeEmpty,contains和remove的程序代码如�?br>

1void makeEmpty()
2 {
3    for( int i=0; i<theLists.size();i++ )
4        theLists[i].clear();
5}
6
7bool contains( const HashedObj &x ) const
8{
9    const list<HashedObj> & whichList = theLists[myhash(x)];
10    return find( whichList.begin(),whichList.end(),x) !=whichList.end();
11}
12
13bool remove( const HashedObj &x )
14{
15    list<HashedObj> &whichList = theLists[myhash(x)];
16    list<HashedObj>::iterator itr = find(whichList.begin(),whichList.end(),x);
17    if( itr == whichList.end() )
18        return false;
19    whichList.erase( itr );
20    --currentSize;
21    return true;
22}

    下一个操作是插入例程。如果要插入的项已经存在�Q�那么什么都不做�Q�否则将其放臌��的前端。该元素可以攑֜�表的��M��地方�Q�此处��用push_back是最方便的。whichList是一个引用变�?br>

1bool insert ( const HashedObj &x )
2{
3    list<HashedObj> & whichList = theLists[ myhash(x) ];
4    if( find( whichList.begin(),whichList.end(),x )!=whichList.end() )
5        return false;
6    whichList.push_back(x);
7
8    if(++currentSize > theLists.size() )
9        rehash();
10
11    return true;
12}

��罗�|?/a> 2009-11-25 22:22 发表评论

Wed, 25 Nov 2009 10:43:00 GMT
摘自阉K��的《这本书�?/span>

1. 开始变得成熟是在最痛苦的时候才换到�?br>
    惌��q�求梦想是在最�I��的时候才军_��?br>
    睡过最舒服的觉是在很篏的时候才发现�?br>
    得过最珍贵的东西是在失�ȝ��时候才知道�?br>
2   惛_��一个�h的时�?距离成了一�U�温�?br>
    ��d��一个�h的时�?距离成了一�U�借口

    ��x��一个�h的时�?心情成了一�U�寂�?br>
    惌��一个�h的时�?寂寞成了一�U��n�?br>
3   �q�个时代房子建得再大

    也装不下那些��x��的�?br>
    �q�个时代房子盖得再小

    也容得下那些惛_��定的�?br>

��罗�|?/a> 2009-11-25 18:43 发表评论