I'm very sorry to tell you that this blog site suspended due to some connectivity issues from my place.
You could check the latest posts on the following site:
http://blog.sina.com.cn/celeron533
Saturday, 9 May 2015
Tuesday, 2 July 2013
Find the Median of a Large Set of Number
Task:
There are 10G disordered numbers, you need to find out the median. You have 2G bytes memory.
Solution:
The simplest method is sorting all numbers then find the middle item:
1 2 3 … 49 50 51 … 98 99 100
There are two defects:
1. Not necessary to sort all numbers
2. Occupies too much memory
Improved:
Create a data table which count the numbers in separated ranges:
(After first scan)
| Range | 1-20 | 21-40 | 41-60 | 61-80 | 81-100 |
| Count | 20 | 20 | 20 | 20 | 20 |
The median must in range [41-60] while the offset is 10 which means the 10th item in the range block is the median
Next, program will scan data set again, and only copy 20 ranged numbers into memory. Do a sort and grab the 10th item.
=======
Assume the numbers are unsigned 64bit integer. So each number occupies 8 bytes. 2G ram could handle no more than 256M numbers each time. The 10G number set could be separated into 40 groups.
Then, define several ranges from 0 to 2^64 -1, looks like arithmetic sequence:
( Pseudo code )
int64 a = 2^64 / 4096;
int64[4096] b ;
Array b statistics the volume of numbers hit in the range. In current code, each b in the array maps a range of 2^64 / 4096 = 2^52
For instance, if there is a number 68846541654532100.
68846541654532100 / (2^52) = 15.287
will lead to:
b[15]++;
The program do a initial process, read 256M numbers each time, for 40 main loops. In each loop, compare function will find out the range of each number and update the b[4096]. When loops done, we will get a full record b[4096].
Find the Median range:
int64 sum=0;
int64 prev=0;
int i;
for (i=0 ; i < 4096 ; i++)
{
prev=sum;
sum += b[i];
if (sum >= 2^64 / 2)
break;
}
int64 offset=(2^64 /2 – prev);
print( i );
Median must located in:
from i*a to (i+1)*a-1
and must be the offset=(2^64 /2 – prev) item in the target block.
Program will scan 10G number set again, but only pick the numbers in the specific range and write them to file system.
IF the final file is less than 2G, sort the content, and pick the ‘offset’ item.
IF the final file is greater than 2G, separate it again as previous steps but smaller range. Do not forget to translate the offset.
Friday, 28 June 2013
Monty Hall problem (Three-Door problem)
http://en.wikipedia.org/wiki/Monty_Hall_problem
The most well known statement of the problem is:
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice? (Whitaker, 1990, as quoted by vos Savant 1990a)
Vos Savant's response was:
Yes; you should switch. The first door has a 1/3 chance of winning, but the second door has a 2/3 chance. Here’s a good way to visualize what happened. Suppose there are a million doors, and you pick door #1. Then the host, who knows what’s behind the doors and will always avoid the one with the prize, opens them all except door #777,777. You’d switch to that door pretty fast, wouldn’t you?
So the ratio between WIN vs LOSE should be 66.6 : 33.3
I spend some time to write a simulator to check. (code is a bit ugly but it works)
Game class:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package montyhallproblem;
/**
*
* @author celeron533
*/
public class Game {
public Door[] doors;
public Game() {
this.doors = new Door[]{new Door(), new Door(), new Door()};//create doors
doors[(int) (Math.random() * 3)].item = Item.car;//allocate the prize
}
public int playerInitial;
public void playerInitialSelection(int s) {
playerInitial = s;
}
public int hostOpenGoatDoor() {
if (doors[playerInitial].item == Item.car) {
//open one door of the rest
int open;
do {
open = (int) (Math.random() * 3);
} while (open == playerInitial);
doors[open].opened = true;
return open;
} else {//when player select a goat door, host open the left goat door
for (int i = 0; i < 3; i++) {
if (i == playerInitial) {//skip player selection
continue;
} else {
if (doors[i].item == Item.car) {//skip car door
continue;
} else {//open
doors[i].opened = true;
return i;
}
}
}
}
return -1;
}
public class Door {
public boolean opened = false;
public Item item = Item.goat;
}
public enum Item {
car, goat
}
@Override
public String toString() {
String result = "select_" + playerInitial + " ";
for (int i = 0; i < 3; i++) {
result += doors[i].item + "_" + doors[i].opened + " ";
}
return result;
}
}
Main class:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package montyhallproblem;
/**
*
* @author celeron533
*/
public class MontyHallProblem {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Game game;
int playerSelect, hostOpen;
int keepSelectionWins = 0;
int switchSelectionWins = 0;
for (int i = 0; i < 10000000; i++) {
game = new Game();
playerSelect = (int) (Math.random() * 3);
game.playerInitialSelection(playerSelect);
hostOpen = game.hostOpenGoatDoor();
//Statistical results
if (game.doors[playerSelect].item == Game.Item.car) {
keepSelectionWins++;
} else {
switchSelectionWins++;
}
//System.out.println(game.toString());
}
System.out.println("keepSelectionWins: " + keepSelectionWins);
System.out.println("switchSelectionWins:" + switchSelectionWins);
}
}
And the perfect result:
run:
keepSelectionWins: 3333349
switchSelectionWins:6666651
BUILD SUCCESSFUL (total time: 3 seconds)
Monday, 10 June 2013
Create a Simple Java REST Web Service Client
A web service is a method of communication between two electronic devices over the World Wide Web. [Wikipedia]
Unlike some private protocol, RESTful web service use common web protocol and encapsulate data into XML format.
For example, client sent a photo search request to flickr:
| http://api.flickr.com/services/rest/?method=flickr.photos.search&api_key=b673a1be26fa7463c7036d9d0e3339e7&text=gundam&format=rest&api_sig=028e6e4f5041b8974069d4ead1f7f2ea |
And flickr will response
<?xml version="1.0" encoding="utf-8" ?> |
===============Create the project in Netbeans=================
Create a new Java Application
Right click on your project –> New –> Other…
In ‘Web Services’ category, select ‘RESTful Java Client’ file
Follow the wizard, java codes and xml schema will be generated automatically.
In NewJerseyClient.java, all APIs are listed. You only need to call the mapped function with proper parameters and the function will raise a connection and make a request.
The Rsp.java is used to unmarsal the XML response.
# Do NOT forget to add the app key in your request.
## Because this in only a very simple example, you need to disable the ‘login’ authority function.
Sample code:
public static void main(String[] args) {
// TODO code application logic here
NewJerseyClient flickrREST = new NewJerseyClient();
RestResponse result = flickrREST.photo_search("gundam");
unmarsal(result.getDataAsString());
}
private static void unmarsal(String xml) {
ByteArrayInputStream stream=new ByteArrayInputStream(xml.getBytes());
Rsp rsp = JAXB.unmarshal(stream, Rsp.class);
System.out.println("Stat:"+rsp.getStat());
Rsp.Photos photos = rsp.getPhotos();
System.out.println("Page:" + photos.getPage() + " Pages:" + photos.getPages()
+ " PerPage:" + photos.getPerpage() + " TotalResults:" + photos.getTotal());
for (Rsp.Photo photo : photos.getPhoto()) {
System.out.println("PhotoID:" + photo.getId() + " Title:" + photo.getTitle());
}
}
===========More works could be done to improve the user interface====
Saturday, 27 April 2013
IT elements in the animation (Part IV)–Evangelion Q
(Part II & Part III are missing. 
They will be completed in the coming weeks)
Evangelion: 3.0 You Can (Not) Redo. (ヱヴァンゲリヲン新劇場版：Q)
A new organization, WILLE, which is NERV’s rival. Start-up its new battleship called “WUNDER” when it encountered the angel.
As an IT guy, it is interesting to inspect the booting screen~
Boot up screen with POST
Here is what on the screen
| SYSTEM SETUP ( STARTUP ) | KhaOS version = 3.00 |
| CONFIGURATION *Device Config = All Devices | HDD CONTROLLER HDD Controller Mode = Auto-Selected |
| I/O PORTS *Serial = COM1(HBK33/BD310) *Parallel = LPT1(RB338/TR9/TB3) *Sound = Enabled | HDD I/O Build-in HDD = Primary ID(1FH000L/IRQ14) = Secondary ID(B1005/IRQ21) = Preliminary ID(CD666/DUMMY SYS.) |
| DISPLAY *Holograph Segment Address = C000HF | |
| KDB BUS *KDB BUS = IRQ | ARCHITECT *Main = Ver.3.10 *3.22Build. *Sub = Ver.3.22 *3.10Build. *Dummy = Ver.6.66 *6.66Build. |
Wait… COM1 LPT1 ?
I haven’t seen them for a long long time
IRQ14 is normally reserved for PATA (IDE) controller
==============
The next scene is the rolling code on the screen.
System is BUSY
Question:
What’s the programing language on the screen?
struct
comment style /* */
code block { }
for [element] in [collection] do {…}
if [condition] then {…}
define a new function by using ‘fn’ keyword
and
local ret = #()
However,
C, C++, C#, Java, JavaScript, VB, BVScript, VBA, python
can not satisfy this coding style
What the hell is that?
New let me try to find out some other keywords.
For example, “EmptyModifier”
Bingo!
It’s MaxScript, from 3ds max.
Completed
All green
Ignite main engine.
Sunday, 14 April 2013
Weekend Project: Miscellaneous
Headphone + Joystick repair.
Both of the equipment is left by former roommate.
Some buttons on panel have no reaction unless you press them firmly. It seems Conductive Rubber under the buttons are dirty.
Teardown the device.
Water wash the buttons/rubber and clean the PCB by using eraser.
Finally, reassemble the joystick and do a test.
=================HeadPhone=============
Logitech headphone.
The volume controller has problem. Even very tiny touch on the controller will mute the right hand side speaker.
Teardown.
At first, I thought just the right-pass of variable resistor is open circuit. Soldering three new ‘Bridge’ will cross the problem.
The Bridge (from another headphone dead body~)
Done. Bridges connected the end-points of tuner
Unfortunately, annoying buzz and mute problem still exists.
I realized it was not a open circuit, but a short circuit. There is an unexpected connection between Right and Ground cable.
Plan B:
Direct connection, no tuner.
Tested, all green.
Mission accomplished.
Wednesday, 6 March 2013
Write a Simple Game with LWJGL (LightWeight Java GL)
This post will show a demo on how to write an OpenGL game by using Java.
LWJGL is a framework not only a java tool package but also contains cross-platform complied OpenGL API files. These native clients could work on the following operation systems: Windows, Linux, MacOSX, and Solaris. Despite Java program efficiency issues, LWJGL gets out a possible solution that developers need only deploy the core code and the rests (OpenGL relative) will auto-adjusted by the framework.
Pong is a very famous & simple console game. So I implement it as the ‘Hello World’ project.
Initially, let me introduce the basic game logic (although most of you know it XD)
- 2 Players (one human and one computer), each player controls a bat
- 1 Ball
- Control the bat move up and down, try to hit the ball, do not miss it
Sketch:
Before we start write code, add LWJGL libraries first.
- Download LWJGL jar files
- Attach these jar files to out project
- Add native GL files to the project. This step is crucial. Select the files which match you current/target operation system
- (optional) Add Javadoc
- Now it should looks like the image below
Great! Ready to work.
============
Firstly, define the entities.
This operation may unnecessary for such small project. But it still helps us to build a well-formed OO program.
Two interfaces: Entity & MoveableEntity
Two abstract classes: AbstractEntity & AbstraceMoveableEntity
Code:
package entites;
public interface Entity {
public void draw();
public void update(int delta);
public void setLocation(double x, double y);
public void setX(double x);
public void setY(double y);
public void setWidth(double width);
public void setHeight(double height);
public double getX();
public double getY();
public double getHeight();
public double getWidth();
public boolean intersects(Entity other);
}
package entites;
import java.awt.Rectangle;
public abstract class AbstractEntity implements Entity {
protected double x, y, width, height;
protected Rectangle hitbox = new Rectangle();
public AbstractEntity(double x, double y, double width, double height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
@Override
public void setLocation(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public void setX(double x) {
this.x = x;
}
@Override
public void setY(double y) {
this.y = y;
}
@Override
public void setWidth(double width) {
this.width = width;
}
@Override
public void setHeight(double height) {
this.height = height;
}
@Override
public double getX() {
return x;
}
@Override
public double getY() {
return y;
}
@Override
public double getHeight() {
return height;
}
@Override
public double getWidth() {
return width;
}
@Override
public boolean intersects(Entity other) {
hitbox.setBounds((int) x, (int) y, (int) width, (int) height);
return hitbox.intersects(other.getX(), other.getY(), other.getWidth(),
other.getHeight());
}
}
package entites;
public interface MoveableEntity extends Entity {
public void setDX(double dx);
public void setDY(double dy);
public double getDX();
public double getDY();
}
package entites;
public abstract class AbstractMoveableEntity extends AbstractEntity implements
MoveableEntity {
protected double dx, dy;
public AbstractMoveableEntity(double x, double y, double width,
double height) {
super(x, y, width, height);
this.dx = 0;
this.dy = 0;
}
@Override
public void update(int delta) {
this.x += delta * dx;
this.y += delta * dy;
}
public void setDX(double dx) {
this.dx = dx;
}
public void setDY(double dy) {
this.dy = dy;
}
public double getDX() {
return dx;
}
public double getDY() {
return dy;
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Time to setup the main body of Pong.
- Initialize OpenGL
- Initialize all necessary Objects
- Make some Objects “move”
- Listening users key-press actions
- Also, AI should response
- Game logic (hit? miss? win? lose?)
- Refresh the screen
The codes are very simple. I believe you can understand most of them.
( Because I am lazy ^_^ )
package pong;
import java.util.Random;
import org.lwjgl.*;
import org.lwjgl.input.Keyboard;
import org.lwjgl.opengl.*;
import entites.AbstractMoveableEntity;
import static org.lwjgl.opengl.GL11.*;
public class PongGame {
public static final int WIDTH = 640, HEIGHT = 480;
private boolean isRunning = true;
private long lastFrame;
private Ball ball;
private Bat bat;
private Bat computerBat;
public PongGame() {
setUpDisplay();
setUpOpenGL();
setUpEntities();
setUpTimer();
while (isRunning) {
render();
logic(getDelta());
input();
computer();
Display.update();
Display.sync(60);
if (Display.isCloseRequested()) {
isRunning = false;
}
}
Display.destroy();
}
private void computer() {
if (ball.getX() > 350 && ball.getDX()>0) {
if (ball.getY() + ball.getHeight() / 2 > computerBat.getY()
+ computerBat.getHeight() / 2 + 4
&& computerBat.getY() + computerBat.getHeight() <= HEIGHT) {
computerBat.setDY(0.2);
} else if (ball.getY() + ball.getHeight() / 2 < computerBat.getY()
+ computerBat.getHeight() / 2 - 4
&& computerBat.getY() >= 0) {
computerBat.setDY(-0.2);
} else {
computerBat.setDY(0);
}
}
else{
computerBat.setDY(0);
}
}
private void input() {
if (Keyboard.isKeyDown(Keyboard.KEY_UP) && bat.getY() >= 0) {
bat.setDY(-0.2);
} else if (Keyboard.isKeyDown(Keyboard.KEY_DOWN)
&& bat.getY() <= HEIGHT - bat.getHeight()) {
bat.setDY(0.2);
} else {
bat.setDY(0);
}
}
public long getTime() {
return (Sys.getTime() * 1000) / Sys.getTimerResolution();
}
public int getDelta() {
long time = getTime();
int delta = (int) (time - lastFrame);
lastFrame = time;
return delta;
}
private void logic(int delta) {
ball.update(delta);
computerBat.update(delta);
bat.update(delta);
//ball hit the bat
if (ball.getX() <= bat.getX() + bat.getWidth()
&& ball.getX() >= bat.getX()
&& ball.getY() + ball.getHeight() >= bat.getY()
&& ball.getY() <= bat.getY() + bat.getHeight()) {
ball.setDX(Math.abs(ball.getDX()));
Random ran = new Random();
ball.setDY(ball.getDY() + bat.getDY() / 3
+ (double) (1 - ran.nextInt(2)) / 200);
}
//ball hit the computerBat
if (ball.getX() + 10 >= computerBat.getX()
&& ball.getX() + 10 <= computerBat.getX() + 10
&& ball.getY() + ball.getHeight() >= computerBat.getY()
&& ball.getY() <= computerBat.getY() + computerBat.getHeight()) {
ball.setDX(-Math.abs(ball.getDX()));
}
//top & bot border
if (ball.getY() < 0 || ball.getY() > HEIGHT - ball.getHeight()) {
ball.setDY(-ball.getDY());
}
if (ball.getX() < 0 || ball.getX() > WIDTH - ball.getWidth()) {
//reset game
setUpEntities();
}
//fix DY if DY is too large
if (Math.abs(ball.getDY()) > Math.abs(ball.getDX() * 1.5)) {
ball.setDY(ball.getDY() / 1.5);
}
}
private void render() {
glClear(GL_COLOR_BUFFER_BIT);
ball.draw();
bat.draw();
computerBat.draw();
}
private void setUpTimer() {
lastFrame = getTime();
}
private void setUpEntities() {
bat = new Bat(20, (HEIGHT / 2 - 80 / 2), 10, 80);
computerBat = new Bat(WIDTH - 20 - 10, (HEIGHT / 2 - 80 / 2), 10, 80);
ball = new Ball(WIDTH / 2 - 10 / 2, HEIGHT / 2 - 10 / 2, 10, 10);
ball.setDX(-0.15);
}
private void setUpOpenGL() {
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0, WIDTH, HEIGHT, 0, 1, -1);
glMatrixMode(GL_MODELVIEW);
}
private void setUpDisplay() {
try {
Display.setDisplayMode(new DisplayMode(WIDTH, HEIGHT));
Display.setTitle("pong");
Display.create();
} catch (LWJGLException e) {
e.printStackTrace();
System.exit(0);
}
}
private static class Bat extends AbstractMoveableEntity {
public Bat(double x, double y, double width, double height) {
super(x, y, width, height);
}
@Override
public void draw() {
//glColor3d(1.0, 1.0, 1.0);
glRectd(x, y, (x + width), (y + height));
}
}
private static class Ball extends AbstractMoveableEntity {
public Ball(double x, double y, double width, double height) {
super(x, y, width, height);
}
@Override
public void draw() {
//glColor3d(1.0, 1.0, 1.0);
glRectd(x, y, x + width, y + height);
}
}
public static void main(String[] args) {
new PongGame();
}
}
Subscribe to:
Posts (Atom)