プログラミング珠玉第一章の授業後の練習問題
1、ライブラリ関数を使用して並べ替え
この異なる言語には異なるライブラリ関数のソートcにqsortがあり、javaにはsortソートがあり、具体的にはコードを貼らない.
2、ビットロジックでビット演算を実現する
この問題の核心は,あるbitを0にし,そのビットを直接0と操作し,あるbitビットを一定に保つために,そのビットと1を操作し,あるbit位置1を1とし,そのビットを1と操作することである.
原書の例i>>SHIFTは、iを32(intは4バイト、32 bit)除いた商がi位がi/32に属するintを得るbitビットの範囲内に相当し、
i&MASKは、i/32を取得する残高、すなわちintのbit範囲の数位に相当します.
4、k個[0,n]の重複しない数字を生成し、k
3、ビットマップの並べ替え(現在の4番目の問題の上で重複しない数字を得てからこの問題をやります)
426040ms
ソート後の出力操作時間が
438ms
5、空きメモリは1 Mあるが、実際のコードは1.25 Mあり、どのようにコードを1 M以内に制御するか.
この問題の核心は、一度に1000000個の数を読み込むとメモリが足りなくなるため、1000000に対してグループ読み込みを行う必要があり、4つのグループに分けると仮定し、まず[0250000000]の範囲の本を読み、並べ替えて出力し、読み込み[250000,000,000,000,000,000,000]の数を並べ替えて、このようにします.方法がわかった以上、まず考えられる最初の問題は、いくつかのグループに分けることです.この問題は比較的簡単な1 Mメモリが8388608 bitで、1つのint 32 bit 8388608/32=261456で、250000に近いので、40グループに分けられます.現在の2番目の問題は、この40グループのデータをどのように読み込むかです.コードは以下の通りです.
この異なる言語には異なるライブラリ関数のソートcにqsortがあり、javaにはsortソートがあり、具体的にはコードを貼らない.
2、ビットロジックでビット演算を実現する
この問題の核心は,あるbitを0にし,そのビットを直接0と操作し,あるbitビットを一定に保つために,そのビットと1を操作し,あるbit位置1を1とし,そのビットを1と操作することである.
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }原書の例i>>SHIFTは、iを32(intは4バイト、32 bit)除いた商がi位がi/32に属するintを得るbitビットの範囲内に相当し、
i&MASKは、i/32を取得する残高、すなわちintのbit範囲の数位に相当します.
4、k個[0,n]の重複しない数字を生成し、k
#include <stdio.h>
#include <windows.h>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#define MAXNUM 10000000
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
int i = 0;
int *tmp = new int[MAXNUM+1];
// 1-MAXNUM LENGTH ， 1-MAXNUM， MAXNUM ，
// r， tmp[i] tmp[r] ，
for(i = 0; i < MAXNUM; i++)
{
tmp[i] = i;
}
for(i = 0;i < MAXNUM; i++)
{
int p = rand();
// rand() RAND_MAX， 10000000， RAND_MAX ， swap(&tmp[i],&tmp[MAXNUM - p])
if(i%2 == 0)
{
swap(&tmp[i],&tmp[p]);
}
else
{
swap(&tmp[i],&tmp[MAXNUM - p]);
}
}
delete[] a;
delete[] tmp;
return 0;
}
3、ビットマップの並べ替え(現在の4番目の問題の上で重複しない数字を得てからこの問題をやります)
#include <stdio.h>
#include <windows.h>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define MAXNUM 10000000
int a[1 + MAXNUM/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
int i = 0;
int *tmp = new int[MAXNUM+1];
// 1-MAXNUM LENGTH ， 1-MAXNUM， MAXNUM ，
// r， tmp[i] tmp[r] ，
for(i = 0; i < MAXNUM; i++)
{
clr(i);
tmp[i] = i;
}
srand((unsigned)time(NULL));
for(i = 0;i < MAXNUM; i++)
{
int p = rand();
if(i%2 == 0)
{
swap(&tmp[i],&tmp[p]);
}
else
{
swap(&tmp[i],&tmp[MAXNUM - p]);
}
}
DWORD start, stop;
start = GetTickCount();
for(i = 0; i < MAXNUM;i++)
set(i);
for(i = 0; i < MAXNUM; i++)
{
if(test(i))
{
printf("%d
",i);
}
}
stop = GetTickCount();
printf("time: %lld ms
", stop - start);
delete[] tmp;
return 0;
}426040ms
ソート後の出力操作時間が
438ms
5、空きメモリは1 Mあるが、実際のコードは1.25 Mあり、どのようにコードを1 M以内に制御するか.
この問題の核心は、一度に1000000個の数を読み込むとメモリが足りなくなるため、1000000に対してグループ読み込みを行う必要があり、4つのグループに分けると仮定し、まず[0250000000]の範囲の本を読み、並べ替えて出力し、読み込み[250000,000,000,000,000,000,000]の数を並べ替えて、このようにします.方法がわかった以上、まず考えられる最初の問題は、いくつかのグループに分けることです.この問題は比較的簡単な1 Mメモリが8388608 bitで、1つのint 32 bit 8388608/32=261456で、250000に近いので、40グループに分けられます.現在の2番目の問題は、この40グループのデータをどのように読み込むかです.コードは以下の通りです.
#include <stdio.h>
#include <windows.h>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#define GROUPNUM 40
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define MAXNUM 10000000
int a[MAXNUM/GROUPNUM+1];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
int i,j,n = 0;
int range = MAXNUM/GROUPNUM;
int *tmp = new int[MAXNUM+1];
// 1-MAXNUM LENGTH ， 1-MAXNUM， MAXNUM ，
// r， tmp[i] tmp[r] ，
for(i = 0; i < MAXNUM; i++)
{
tmp[i]=i;
}
srand((unsigned)time(NULL));
for(i = 0;i < MAXNUM; i++)
{
int p = rand();
if(i%2 == 0)
{
swap(&tmp[i],&tmp[p]);
}
else
{
swap(&tmp[i],&tmp[MAXNUM - p]);
}
}
DWORD start, stop;
start = GetTickCount();
//
for(i = 0; i < GROUPNUM; i++)
{
//
for(j = 0; j < range; j++)
{
clr(j);
}
// [range*i,range*i+range)
for(j = 0; j < MAXNUM; j++)
{
if(range*i <= tmp[j] && tmp[j] < range*(i+1))
{
set(tmp[j]%range);
}
}
// [range*i,range*i+range)
for(j = 0; j < range; j++)
{
if(test(j))
{
printf("%d
",j);
}
}
}
stop = GetTickCount();
printf("time: %lld ms
", stop - start);
delete[] tmp;
return 0;
}
ソート を するとprintf("%d
",j);
は3250 msパケット のみでメモリ の は したが, にすべてのデータを 40 し, に した.
6もし1つの が1 だけではないならば、10が れることができて、どのようにします
この は は 5 のアップグレード で、 のメモリを けて を することに して、 りのメモリは 5 の によって をグループ して べ えて、1つの は 10 れて、4 bitビットが1つの の を することに して、4*10^7 の を けます.
7、
1つの を し、test(i)がtrueを たと した 、この の み りを し、0より きい は、 をするときに することができ、 ではなく み まなくてもよい.
8、もし の が8008877888があるならば、メモリは として1 Mだけあって、どのように べ えます
この は が えることができるのは、1つの の の を むたびにソートするだけで、 の4 の とあまり がありません.
9、 の をどのように いて、 めてこのベクトルにアクセスするたびに することを します.
この はネット のgoogleでやっと えの を した. な は、2つの from toと1つの top=0を することである.if(from[i] < top && to[from[i]] == i)
{
printf("has used!
")
}
else
{
a[i] = 1;
from[i] = top;
to[top] = i;
top++;
}
top は、 された の を するために され、from[i]=topは、a[i]がいくつかの された であることを することに し、to[top]=iは、top の を するために される がdataの にどれだけあるかを す.したがって、1つのdata にアクセスするたびに、from[i]10、 コストの まで、 は が で を し、 に して で ることを した.ショップ・データベースは、 の を の なキーワードとして します( は を っており、これらのキーワードはほとんど です).どのようにしてショップのデータベースを して、 な と を にしますか?
の の2 が のハッシュインデックスとして され、 が で したとき、 な に かれる.そして、 が して を すると、 は に を します.これは、ハッシュ を する な です. に します. の の2 の はかなりランダムで、 の 2 はインデックスとして じません. くの の 2 は じですから.
11、 つのデータ を してコストを する
えはハトに わって、 にはハトがこんなに い を って べると いますか?この は な に ているようだ.
12、 で なペンを く
この はずいぶん に いたようです. です.